题目描述
求一个数组的子数组最大和
例如[3,-2,1,6,-9,1,2,3]
那么这个数组的子数组最大和为8[3,-2,1,6]
[leetcode53]https://leetcode.com/problems/maximum-subarray/
思路：
- 首先当然可以暴力的使用两层循环找到这个最大的子数组，但是太费时间了。
- 动态规划来求解
算法流程
- 使用两个变量cur和res,cur代表求解过程中的一个临时变量，代表累加到当前位置的一个片段最大，res代表全局的最大，实时更新。
- 遍历数组，cur为数组元素的累加和，如果cur<0，先把cur置为0，然后cur加上当前位置元素，并比较cur和res的大小，更新res。遍历结束后返回res即可。
算法原理
思考位置i,如果在位置i cur大于0，证明你从i位置开始的最大和肯定没有从i之前开始的大,假如你cur<0了，那么从i 开始肯定比从i之前开始大，因为你前缀为负数，为何不直接丢弃前缀呢。所以有了我们算法的更新策略。
代码
public class Solution {
public int maxSubArray(int[] nums) {
if(nums==null||nums.length==0)
return 0;
int cur=nums[0];
int res=nums[0];
for(int i=1;i<nums.length;i++){
cur=cur<0?0:cur;
cur+=nums[i];
res=Math.max(cur,res);
}
return res;
}
}
