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

1
class Solution {
2
 public:
3
  vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
4
    int n = nums.size();
5
    vector<int> prefixSum(n + 1, 0);
6

7
    for (int i = 1; i <= n; i++) {
8
      prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
9
    }
10

11
    vector<int> left(n + 1, 0);
12
    vector<int> leftInd(n + 1, 0);
13
    vector<int> right(n + 1, 0);
14
    vector<int> rightInd(n + 1, 0);
15

16
    for (int i = k; i <= n; i++) {
17
      left[i] = max(left[i - 1], prefixSum[i] - prefixSum[i - k]);
18

19
      if (left[i] == left[i - 1]) {
20
        leftInd[i] = leftInd[i - 1];
21
      } else {
22
        leftInd[i] = i;
23
      }
24
    }
25

26
    for (int i = n - k; i >= 0; i--) {
27
      right[i] = max(right[i + 1], prefixSum[i + k] - prefixSum[i]);
28

29
      if (right[i] == prefixSum[i + k] - prefixSum[i]) {
30
        rightInd[i] = i;
31
      } else {
32
        rightInd[i] = rightInd[i + 1];
33
      }
34
    }
35

36
    int maxSum = 0, a, b, c;
37

38
    for (int i = k; i <= n - 2 * k; i++) {
39
      if (maxSum < left[i] + (prefixSum[i + k] - prefixSum[i]) + right[i + k]) {
40
        maxSum = left[i] + (prefixSum[i + k] - prefixSum[i]) + right[i + k];
41
        a = leftInd[i] - k;
42
        b = i;
43
        c = rightInd[i + k];
44
      }
45
    }
46

47
    return {a, b, c};
48
  }
49
};