0689. Maximum Sum of 3 Non-Overlapping Subarrays

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays

Description

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)

ac

divide and conquer, scan twice

Similar with this but not the same: https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108231/C%2B%2BJava-DP-with-explanation-O(n)

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        // edge cases
        if (nums == null || nums.length == 0 || nums.length < 3 * k) {
            return new int[0];
        }

        // get subarray sum
        int[] subsum = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            subsum[0] += nums[i];
        }
        for (int i = 1; i < subsum.length; i++) {
            subsum[i] = subsum[i-1] - nums[i-1] + nums[i+k-1];
        }

        // dp, left[i], right[i]
        int[] left = new int[subsum.length];  // maximum to the left
        int[] right = new int[subsum.length];  // maximun to the right

        int max = 0;
        for (int i = 0; i < left.length; i++) {
            int i2 = i - k;
            if (i2 < 0) {
                left[i] = -1;
                continue;
            }
            if (subsum[i2] > subsum[max]) max = i2;  // update max value and index
            left[i] = max;
        }

        max = subsum.length - 1;
        for (int i = subsum.length - 1; i >= 0; i--) {
            int i2 = i + k;
            if (i2 >= subsum.length) {
                right[i] = -1;
                continue;
            }
            if (subsum[i2] >= subsum[max]) max = i2;
            right[i] = max;
        }

        // get result
        long maxSum = Long.MIN_VALUE;
        int[] res = new int[3];
        for (int i = 0; i < subsum.length; i++) {
            if (left[i] == -1 || right[i] == -1) continue;
            long tmpSum = subsum[left[i]] + subsum[i] + subsum[right[i]];
            if (tmpSum > maxSum) {  // update max
                maxSum = tmpSum;
                res[0] = left[i];
                res[1] = i;
                res[2] = right[i];
            }
        }

        return res;
    }
}

ac2:

Don't even understand by looking at it. Impossible to figure out in the interview.

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] res = new int[3];
        // edge cases
        if (nums == null || nums.length == 0 || k <= 0 || nums.length / k < 3) return res;

        int n = nums.length;
        int xSubarrays = 3; // x means how many subarrays
        int[][] max = new int[xSubarrays+1][n+1];
        int[][] idx = new int[xSubarrays+1][n+1];
        int[] sum = new int[n+1];

        // init accumulation sum, in order to get subarray sum
        for (int i = 1; i < sum.length; i++) sum[i] = sum[i-1] + nums[i-1];

        // iterate
        for (int x = 1; x <= xSubarrays; x++) {
            for (int i = x * k; i < max[0].length; i++) {
                int tmp = max[x-1][i-k] + (sum[i] - sum[i-k]);
                if (tmp > max[x][i-1]) { // find greater sum, update info
                    max[x][i] = tmp;
                    idx[x][i] = i - k;
                } else {
                    max[x][i] = max[x][i-1];
                    idx[x][i] = idx[x][i-1];
                }
            }
        }

        // get indices
        res = new int[xSubarrays];
        res[xSubarrays-1] = idx[xSubarrays][n];
        for (int i = xSubarrays - 2; i >= 0; i--) {
            int prevIdx = res[i+1];
            res[i] = idx[i+1][prevIdx];
        }

        return res;
    }
}

/*
so hard to understand the indices, a better approach is to have an example
*/