题目描述：
给出一个长度为 $n$ 的整数数组nums和两个整数firstLen和secondLen，请找出并返回两个非重叠子数组中元素的最大和，长度分别为firstLen,secondLen。二者不能重叠，前后顺序可变。
数据范围：
$1\le firstLen,secondLen \le 1000;firstLen+secondLen\le n \le 1000$
题解：
假设firstLen在secondLen之前，那么可以枚举secondLen的起点 $i$ ，使用dp维护前面 $[1, i - 1]$ 中长度为 $firstLen$ 子数组的最大值，则答案为：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e3 + 1;
int dp[maxn];
int sum[maxn];
int n;
int getSum(int l, int r)
{
return sum[r] - sum[l - 1];
}
int solve(int firstLen, int secondLen)
{
memset(dp, 0, sizeof(dp));
int ans = 0;
for (int i = 1; i + secondLen - 1 <= n; ++i)
{
if (i > firstLen)
{
dp[i] = max(dp[i - 1], getSum(i - firstLen, i - 1));
ans = max(ans, dp[i] + getSum(i, i + secondLen - 1));
}
}
return ans;
}
int maxSumTwoNoOverlap(vector<int> &nums, int firstLen, int secondLen)
{
n = nums.size();
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + nums[i - 1];
}
return max(solve(firstLen, secondLen), solve(secondLen, firstLen));
}
};
|