image.png
解題思路
首先看清題目
求連續(xù)子序列
可以考慮動態(tài)規(guī)劃，dp[i]來保存陷猫，前i個數(shù)字的連續(xù)序列和
如果dp[i-1]>0秫舌，說明可以繼續(xù)加元素，dp[i]=nums[i]+dp[i-1]
如果dp[I-1]<=0,說明從當(dāng)前第i個元素開始累加
剩余的來看注釋
為什么需要int max=nums[0];绣檬？
如果輸入為[-2,-1],但max默認(rèn)初始值為0足陨，在max=Math.max(max,dp[i])，比較時娇未，可能出現(xiàn)max=0墨缘，這樣不符合題意
為什么dp[0]=nums[0];？
因為遍歷是從第2個元素開始的零抬，所以遍歷第二個元素時镊讼，會比較dp[i-1]>0是否成立，否則的話dp[0]=0平夜，該等式永遠(yuǎn)不成立
不符合題意
代碼
class Solution {
public int maxSubArray(int[] nums) {
int a=nums.length;
int [] dp=new int[a];
int max=nums[0];
dp[0]=nums[0];
if(a==1) return nums[0];
for(int i=1;i<a;i++){
if(dp[i-1]>0) dp[i]=nums[i]+dp[i-1];
else dp[i]=nums[i];
max=Math.max(max,dp[i]);//獲取最大值
}
return max;
}
}
