Skip to content

689. Maximum Sum of 3 Non-Overlapping Subarrays 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
44
45
46
47
class Solution {
 public:
  vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    const int n = nums.size() - k + 1;
    // sums[i] := sum(nums[i..i + k))
    vector<int> sums(n);
    // l[i] := the index in [0..i] that has the maximum sums[i]
    vector<int> l(n);
    // r[i] := the index in [i..n) that has the maximum sums[i]
    vector<int> r(n);

    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      if (i >= k)
        sum -= nums[i - k];
      if (i >= k - 1)
        sums[i - k + 1] = sum;
    }

    int maxIndex = 0;
    for (int i = 0; i < n; ++i) {
      if (sums[i] > sums[maxIndex])
        maxIndex = i;
      l[i] = maxIndex;
    }

    maxIndex = n - 1;
    for (int i = n - 1; i >= 0; --i) {
      if (sums[i] >= sums[maxIndex])
        maxIndex = i;
      r[i] = maxIndex;
    }

    vector<int> ans{-1, -1, -1};

    for (int i = k; i < n - k; ++i)
      if (ans[0] == -1 || sums[ans[0]] + sums[ans[1]] + sums[ans[2]] <
                              sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
        ans[0] = l[i - k];
        ans[1] = i;
        ans[2] = r[i + k];
      }

    return ans;
  }
};

 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
44
45
46
class Solution {
  public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    final int n = nums.length - k + 1;
    // sums[i] := sum(nums[i..i + k))
    int[] sums = new int[n];
    // l[i] := the index in [0..i] that has the maximum sums[i]
    int[] l = new int[n];
    // r[i] := the index in [i..n) that has the maximum sums[i]
    int[] r = new int[n];

    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
      sum += nums[i];
      if (i >= k)
        sum -= nums[i - k];
      if (i >= k - 1)
        sums[i - k + 1] = sum;
    }

    int maxIndex = 0;
    for (int i = 0; i < n; ++i) {
      if (sums[i] > sums[maxIndex])
        maxIndex = i;
      l[i] = maxIndex;
    }

    maxIndex = n - 1;
    for (int i = n - 1; i >= 0; --i) {
      if (sums[i] >= sums[maxIndex])
        maxIndex = i;
      r[i] = maxIndex;
    }

    int[] ans = {-1, -1, -1};

    for (int i = k; i + k < n; ++i)
      if (ans[0] == -1 ||
          sums[ans[0]] + sums[ans[1]] + sums[ans[2]] < sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
        ans[0] = l[i - k];
        ans[1] = i;
        ans[2] = r[i + k];
      }

    return ans;
  }
}

 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
class Solution:
  def maxSumOfThreeSubarrays(self, nums: list[int], k: int) -> list[int]:
    n = len(nums) - k + 1
    # sums[i] := sum(nums[i..i + k))
    sums = [0] * n
    # l[i] := the index in [0..i] that has the maximum sums[i]
    l = [0] * n
    # r[i] := the index in [i..n) that has the maximum sums[i]
    r = [0] * n

    summ = 0
    for i, num in enumerate(nums):
      summ += num
      if i >= k:
        summ -= nums[i - k]
      if i >= k - 1:
        sums[i - k + 1] = summ

    maxIndex = 0
    for i in range(n):
      if sums[i] > sums[maxIndex]:
        maxIndex = i
      l[i] = maxIndex

    maxIndex = n - 1
    for i in range(n - 1, -1, -1):
      if sums[i] >= sums[maxIndex]:
        maxIndex = i
      r[i] = maxIndex

    ans = [-1, -1, -1]

    for i in range(k, n - k):
      if (ans[0] == -1 or
          sums[ans[0]] + sums[ans[1]] + sums[ans[2]] <
              sums[l[i - k]] + sums[i] + sums[r[i + k]]):
        ans[0] = l[i - k]
        ans[1] = i
        ans[2] = r[i + k]

    return ans