题目链接:53. 最大子数组和
这个和560. 和为 K 的子数组类似,这种求子数组和用前缀和解决较为简单,前缀和的核心思想是用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;
}
}
标签:pre,遍历,前缀,int,53,数组,最大
From: https://www.cnblogs.com/keaqi/p/18144778