53. 最大子数组和

题目链接：53. 最大子数组和 (opens new window)

这个和560. 和为 K 的子数组 (opens new window)类似，这种求子数组和用前缀和解决较为简单，前缀和的核心思想是用pre[i]表示[0,i]的子数组和，则[i,j]的子数组和为pre[j]-pre[i-1]。在560中，遍历到j时找pre[j]-pre[i-1]=K的子数组就是找在j之前等于pre[j]-K的前缀和，所以要存储每一步的前缀和。

说回本题，要让子数组和pre[j]-pre[i-1]最大，遍历到j时，pre[j]已经固定了，让pre[i-1]最小即可求出j作为右边界对应的最大子数组和，因此在遍历时要维护一个当前索引之前的最小子数组和的变量，遍历每个索引都可以得到一个将其作为右边界的最小子数组和，最终取其中最大的即可。代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int minpre=0;//当前索引j前的最小[0,i](i<j)子数组和
        int res=-10000;
        int pre=0;
        for(int i:nums){
            pre+=i;//统计前缀和            
            res=Math.max(res,pre-minpre);//更新最大子数组和
            minpre=Math.min(minpre,pre);//更新最小前缀子数组和
        }
        return res;
    }
}