689. Maximum Sum of 3 Non-Overlapping Subarrays

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

 Example 1:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2,1], k = 2
Output: [0,2,4]

 Constraints:

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

Solution 1: Sliding Window

Solution 2: Preprocessing Prefix and Suffix + Enumerating Middle Subarray

C++

• class Solution {
  public:
      vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
          int n = nums.size();
          vector<int> s(n + 1, 0);
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + nums[i];
          }
  
          vector<vector<int>> pre(n, vector<int>(2, 0));
          vector<vector<int>> suf(n, vector<int>(2, 0));
  
          for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
              int cur = s[i + k] - s[i];
              if (cur > t) {
                  pre[i + k - 1] = {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  pre[i + k - 1] = {t, idx};
              }
          }
  
          for (int i = n - k, t = 0, idx = 0; i >= 0; --i) {
              int cur = s[i + k] - s[i];
              if (cur >= t) {
                  suf[i] = {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  suf[i] = {t, idx};
              }
          }
  
          vector<int> ans;
          for (int i = k, t = 0; i < n - 2 * k + 1; ++i) {
              int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
              if (cur > t) {
                  ans = {pre[i - 1][1], i, suf[i + k][1]};
                  t = cur;
              }
          }
  
          return ans;
      }
  };

JAVA

• class Solution {
      public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
          int n = nums.length;
          int[] s = new int[n + 1];
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + nums[i];
          }
          int[][] pre = new int[n][0];
          int[][] suf = new int[n][0];
          for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
              int cur = s[i + k] - s[i];
              if (cur > t) {
                  pre[i + k - 1] = new int[] {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  pre[i + k - 1] = new int[] {t, idx};
              }
          }
          for (int i = n - k, t = 0, idx = 0; i >= 0; --i) {
              int cur = s[i + k] - s[i];
              if (cur >= t) {
                  suf[i] = new int[] {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  suf[i] = new int[] {t, idx};
              }
          }
          int[] ans = new int[0];
          for (int i = k, t = 0; i < n - 2 * k + 1; ++i) {
              int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
              if (cur > t) {
                  ans = new int[] {pre[i - 1][1], i, suf[i + k][1]};
                  t = cur;
              }
          }
          return ans;
      }
  }

PYTHON

• class Solution {
  public:
      vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
          int n = nums.size();
          vector<int> s(n + 1, 0);
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + nums[i];
          }
  
          vector<vector<int>> pre(n, vector<int>(2, 0));
          vector<vector<int>> suf(n, vector<int>(2, 0));
  
          for (int i = 0, t = 0, idx = 0; i < n - k + 1; ++i) {
              int cur = s[i + k] - s[i];
              if (cur > t) {
                  pre[i + k - 1] = {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  pre[i + k - 1] = {t, idx};
              }
          }
  
          for (int i = n - k, t = 0, idx = 0; i >= 0; --i) {
              int cur = s[i + k] - s[i];
              if (cur >= t) {
                  suf[i] = {cur, i};
                  t = cur;
                  idx = i;
              } else {
                  suf[i] = {t, idx};
              }
          }
  
          vector<int> ans;
          for (int i = k, t = 0; i < n - 2 * k + 1; ++i) {
              int cur = s[i + k] - s[i] + pre[i - 1][0] + suf[i + k][0];
              if (cur > t) {
                  ans = {pre[i - 1][1], i, suf[i + k][1]};
                  t = cur;
              }
          }
  
          return ans;
      }
  };