今天為大家講解 LeetCode 第 53 題，繼續為大家帶來一道常考的數組題目。
題目描述給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],輸出: 6解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。進階:
如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/maximum-subarray著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路 動態規划動態規劃的是首先對數組進行遍歷，當前最大連續子序列和為 sum，結果為 ans如果 sum > 0，則說明 sum 對結果有增益效果，則 sum 保留並加上當前遍歷數字如果 sum <= 0，則說明 sum 對結果無增益效果，需要捨棄，則 sum 直接更新為當前遍歷數字每次比較 sum 和 ans 的大小，將最大值置為ans，遍歷結束返回結果遍歷一次，時間複雜度為 O(n)
空間複雜度為O(1)
圖解如下
代碼實現//go
func maxSubArray(nums []int) int {
ans := nums[0]
sum := 0
for _, val := range nums {
if sum > 0 {
sum += val
}else {
sum = val
}
ans = max(ans, sum)
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
}鄭重聲明：
所展示代碼已通過 LeetCode 運行通過，請放心食用～
在嘮嘮嗑很多人都想養成好習慣，但大多數人卻是三分鐘熱度。為了我們能一起堅持下去，決定製定如下計劃（福利）
一起學算法，打卡領紅包！
參與方式：
關注我的微信公眾號「Kevin的學堂」
還可「加群」與眾多小夥伴
一起堅持，一起學習，一起更優秀！
打卡規則為：
「留言」「打卡XXX天」 ➕「分享」到朋友圈
獎勵：
連續打卡 21 天，聯繫本人獲取 6.6 元紅包一個！
連續打卡 52 天，聯繫本人獲取 16.6 元紅包一個！
連續打卡 100 天，聯繫本人獲取 66.6 元紅包一個！
長按掃碼，一起進步
推薦閱讀
站長 polarisxu
自己的原創文章
不限於 Go 技術
職場和創業經驗
Go語言中文網
每天為你
分享 Go 知識
Go愛好者值得關注