题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：
定义：
sum：累加和
max：和的最大值
遍历数组nums
1.nums[i] 赋给sum
2.如果sum<0，则sum保留原值，否则下一个元素的值 加上 sum
3.如果sum > max,则 max = sum，更新sum
代码：
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (sum >= 0)
sum = nums[i] + sum;
else
sum = nums[i];
if (sum > max)
max = sum;
}
return max;
}
总结
动态规划题
