LeetCode Solutions

			

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;
  }
};

			

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;
  }
}

			

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))