Apple 手机网站制作,百度一下官网页,建设银行永泰支行网站,教育网站官网力扣1031. 两个非重叠子数组的最大和
题目解析及思路
题目要求找到两段长分别为firstLen 和 secondLen的子数组#xff0c;使两段元素和最大
图解见灵神
枚举第二段区间的右端点#xff0c;在左边剩余部分中找出元素和最大的第一段区间#xff0c;并用前缀和优化求子数组…力扣1031. 两个非重叠子数组的最大和
题目解析及思路
题目要求找到两段长分别为firstLen 和 secondLen的子数组使两段元素和最大
图解见灵神
枚举第二段区间的右端点在左边剩余部分中找出元素和最大的第一段区间并用前缀和优化求子数组元素和
代码
class Solution {
public:int maxSumTwoNoOverlap(vectorint nums, int firstLen, int secondLen) {int ans 0,n nums.size(),s[n1];s[0] 0;//求前缀和for(int i1;in;i)s[i] s[i-1] nums[i-1];auto f [](int firstLen,int secondLen){int maxsum 0;//枚举第二段区间右端点for(int i firstLensecondLen;in;i){//求第一段区间最大值maxsum max(maxsum,s[i-secondLen] - s[i-secondLen-firstLen]);ans max(ans,maxsum s[i] - s[i-secondLen]);}};//左a右bf(firstLen,secondLen);//左b右af(secondLen,firstLen);return ans;}
};
