给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路
以dp[i]表示以nums[i]为结尾的序列的最大序列和，对于以nums[i]为结尾的序列，只有两种情况：
1.是多个数组成的序列，和为dp[i-1]+nums[i],
2.是只有nums[i]一个数的序列，和为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;
}
}
