Skip to content

1031. Maximum Sum of Two Non-Overlapping Subarrays 👍

  • Time:
  • Space: 
 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
class Solution {
 public:
  int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
    return max(helper(nums, firstLen, secondLen),
               helper(nums, secondLen, firstLen));
  }

 private:
  int helper(vector<int>& A, int l, int r) {
    const int n = A.size();
    vector<int> left(n);
    int sum = 0;

    for (int i = 0; i < n; ++i) {
      sum += A[i];
      if (i >= l)
        sum -= A[i - l];
      if (i >= l - 1)
        left[i] = i > 0 ? max(left[i - 1], sum) : sum;
    }

    vector<int> right(n);
    sum = 0;

    for (int i = n - 1; i >= 0; --i) {
      sum += A[i];
      if (i <= n - r - 1)
        sum -= A[i + r];
      if (i <= n - r)
        right[i] = i < n - 1 ? max(right[i + 1], sum) : sum;
    }

    int ans = 0;

    for (int i = 0; i < n - 1; ++i)
      ans = max(ans, left[i] + right[i + 1]);

    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
class Solution {
  public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
    return Math.max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
  }

  private int helper(int[] A, int l, int r) {
    final int n = A.length;
    int[] left = new int[n];
    int sum = 0;

    for (int i = 0; i < n; ++i) {
      sum += A[i];
      if (i >= l)
        sum -= A[i - l];
      if (i >= l - 1)
        left[i] = i > 0 ? Math.max(left[i - 1], sum) : sum;
    }

    int[] right = new int[n];
    sum = 0;

    for (int i = n - 1; i >= 0; --i) {
      sum += A[i];
      if (i <= n - r - 1)
        sum -= A[i + r];
      if (i <= n - r)
        right[i] = i < n - 1 ? Math.max(right[i + 1], sum) : sum;
    }

    int ans = 0;

    for (int i = 0; i < n - 1; ++i)
      ans = Math.max(ans, left[i] + right[i + 1]);

    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
class Solution:
  def maxSumTwoNoOverlap(
      self,
      nums: list[int],
      firstLen: int,
      secondLen: int,
  ) -> int:
    def helper(l: int, r: int) -> int:
      n = len(nums)
      left = [0] * n
      summ = 0

      for i in range(n):
        summ += nums[i]
        if i >= l:
          summ -= nums[i - l]
        if i >= l - 1:
          left[i] = max(left[i - 1], summ) if i > 0 else summ

      right = [0] * n
      summ = 0

      for i in reversed(range(n)):
        summ += nums[i]
        if i <= n - r - 1:
          summ -= nums[i + r]
        if i <= n - r:
          right[i] = max(right[i + 1], summ) if i < n - 1 else summ

      return max(left[i] + right[i + 1] for i in range(n - 1))

    return max(helper(firstLen, secondLen), helper(secondLen, firstLen))