給定一個整數(shù)數(shù)組 nums 枣氧，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和截粗。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大信姓，為 6。
思路
以dp[i]表示以nums[i]為結(jié)尾的序列的最大序列和绸罗，對于以nums[i]為結(jié)尾的序列意推，只有兩種情況：
1.是多個數(shù)組成的序列，和為dp[i-1]+nums[i],
2.是只有nums[i]一個數(shù)的序列珊蟀，和為nums[i]
class Solution {
public int maxSubArray(int[] nums) {
int[] dp=new int[nums.length];
dp[0]=nums[0];
int max=dp[0];
for(int i=1;i<nums.length;++i){
if(dp[i-1]>0){
dp[i]=nums[i]+dp[i-1];
}else{
dp[i]=nums[i];
}
if(max<dp[i]){
max=dp[i];
}
}
return max;
}
}
class Solution {
public int maxSubArray(int[] nums) {
int[] dp=new int[nums.length];
dp[0]=nums[0];
for(int i=1;i<nums.length;++i){
if(dp[i-1]+nums[i]>nums[i]){
dp[i]=dp[i-1]+nums[i];
}else{
dp[i]=nums[i];
}
}
int max=dp[0];
for(int i=1;i<nums.length;++i){
if(dp[i]>max){
max=dp[i];
}
}
return max;
}
}
