WordPress建立电商网站日结app推广联盟

力扣1031. 两个非重叠子数组的最大和

题目解析及思路

题目要求找到两段长分别为firstLen 和 secondLen的子数组，使两段元素和最大

图解见灵神

枚举第二段区间的右端点，在左边剩余部分中找出元素和最大的第一段区间，并用前缀和优化求子数组元素和

代码

class Solution {
public:int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {int ans = 0,n = nums.size(),s[n+1];s[0] = 0;//求前缀和for(int i=1;i<=n;i++)s[i] = s[i-1] + nums[i-1];auto f = [&](int firstLen,int secondLen){int maxsum = 0;//枚举第二段区间右端点for(int i = firstLen+secondLen;i<=n;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;}
};