Maximum Sum of Two Non-Overlapping Subarrays LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(vector<int> &prefixSum, int n, int firstLen, int secondLen) {
4
    vector<int> dp(n, 0);
5

6
    dp[n - secondLen] = prefixSum[n] - prefixSum[n - secondLen];
7

8
    for (int i = n - secondLen - 1; i >= 0; i--) {
9
      dp[i] = max(dp[i + 1], prefixSum[i + secondLen] - prefixSum[i]);
10
    }
11

12
    dp[firstLen] = dp[firstLen] + prefixSum[firstLen] - prefixSum[0];
13

14
    for (int i = firstLen + 1; i <= n - secondLen; i++) {
15
      dp[i] = max(dp[i - 1], dp[i] + (prefixSum[i] - prefixSum[i - firstLen]));
16
    }
17

18
    return *max_element(dp.begin(), dp.end());
19
  }
20

21
  int maxSumTwoNoOverlap(vector<int> &nums, int firstLen, int secondLen) {
22
    int n = nums.size();
23
    vector<int> prefixSum(n + 1, 0);
24

25
    for (int i = 1; i <= n; i++) {
26
      prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
27
    }
28

29
    return max(solve(prefixSum, n, firstLen, secondLen), solve(prefixSum, n, secondLen, firstLen));
30
  }
31
};