給定一個(gè)整數(shù)數(shù)組 nums 汰具，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和幔荒。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大但荤，為 6娜谊。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法属划，嘗試使用更為精妙的分治法求解恬叹。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)同眯，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處绽昼。
解答參考以下作者,真的是太強(qiáng)了吧,看答案都想了好久才理清
作者：guanpengchn
鏈接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)须蜗，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處硅确。
- 思路
動(dòng)態(tài)規(guī)劃的是首先對(duì)數(shù)組進(jìn)行遍歷目溉，當(dāng)前最大連續(xù)子序列和為 sum，結(jié)果為 ans
如果 sum > 0菱农，則說明 sum 對(duì)結(jié)果有增益效果缭付，則 sum 保留并加上當(dāng)前遍歷數(shù)字
如果 sum <= 0，則說明 sum 對(duì)結(jié)果無增益效果大莫，需要舍棄蛉腌，則 sum 直接更新為當(dāng)前遍歷數(shù)字
每次比較 sum 和 ans的大小官份，將最大值置為ans只厘，遍歷結(jié)束返回結(jié)果
// created by fivezm on 20,7 2019
public static int maxSubArray(int[] nums) {
int ans = nums[0]; // 假設(shè) 數(shù)組的第一個(gè)元素時(shí)最大的,是答案
int sum = 0; // sum 為子序列相加的和
for (int num : nums) {
if (sum > 0) { // 如果子序列大于0,則證明對(duì)答案有正增長,將它們累加起來
sum += num;
} else { // 如果子序列小于等于0,則證明對(duì)答案有負(fù)增長或無增長,這是要舍棄之前的sum,重新將這一個(gè)num元素設(shè)置為子序列的第一個(gè)
sum = num;
}
ans = Math.max(ans, sum); // ans有可能是最大的,,累加得到的sum也有可能是最大的,那么要判斷一下哪一個(gè)最大,賦值給ans變量,因?yàn)閟um變量是一直都在變
}
return ans;
}
