LeetCode Solutions

			

class Solution {
 public:
  vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    const int n = nums.size() - k + 1;
    vector<int> sums(n);  // sums[i] := sum of nums[i..i + k)
    vector<int> l(n);     // l[i] := index in [0..i] having max sums[i]
    vector<int> r(n);     // r[i] := index in [i..n) having max sums[i]

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

			

class Solution {
  public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    final int n = nums.length - k + 1;
    int[] sums = new int[n]; // sums[i] := sum of nums[i..i + k)
    int[] l = new int[n];    // l[i] := index in [0..i] having max sums[i]
    int[] r = new int[n];    // r[i] := index in [i..n) having max sums[i]

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

			

class Solution:
  def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
    ans = [-1] * 3
    subarrayCount = len(nums) - k + 1
    dp = [0] * subarrayCount
    summ = 0

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

    left = [0] * subarrayCount
    maxIndex = 0

    for i in range(subarrayCount):
      if dp[i] > dp[maxIndex]:
        maxIndex = i
      left[i] = maxIndex

    right = [0] * subarrayCount
    maxIndex = subarrayCount - 1

    for i in reversed(range(subarrayCount)):
      if dp[i] >= dp[maxIndex]:
        maxIndex = i
      right[i] = maxIndex

    for i in range(k, subarrayCount - k):
      if ans[0] == -1 or dp[left[i - k]] + dp[i] + dp[right[i + k]] > dp[ans[0]] + dp[ans[1]] + dp[ans[2]]:
        ans = [left[i - k], i, right[i + k]]

    return ans