53. Maximum Subarray
面試的時候考到了候齿，動態(tài)規(guī)劃最優(yōu)熙暴。O（n）
提升一點小難度闺属，加法變乘法152. Maximum Product Subarray
最大連續(xù)子序列和，非常經(jīng)典的題周霉。
當(dāng)我們從頭到尾遍歷這個數(shù)組的時候掂器，對于數(shù)組里的一個整數(shù)，它有幾種選擇呢俱箱？它只有兩種選擇： 1国瓮、加入之前的SubArray；2. 自己另起一個SubArray狞谱。
那什么時候會出現(xiàn)這兩種情況呢乃摹？
如果之前SubArray的總體和大于0的話，我們認(rèn)為其對后續(xù)結(jié)果是有貢獻(xiàn)的跟衅。這種情況下我們選擇加入之前的SubArray
如果之前SubArray的總體和為0或者小于0的話孵睬，我們認(rèn)為其對后續(xù)結(jié)果是沒有貢獻(xiàn)，甚至是有害的（小于0時）伶跷。這種情況下我們選擇以這個數(shù)字開始掰读，另起一個SubArray。
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) return 0;
int sumPre = nums[0];
int globalMax = nums[0];
for(int i = 1; i< nums.length; i++){
sumPre = Math.max(sumPre+ nums[i], nums[i]); //continue a subarray, or start a new subarry
globalMax = Math.max(sumPre , globalMax);//compare with all
}
return globalMax;
}
}
除了DP還可以思考一些其他思路
