In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

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:

Input: [1,2,1,2,6,7,5,1], 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. 

Note:

nums.length will be between 1 and 20000.
nums[i] will be between 1 and 65535.
k will be between 1 and floor(nums.length / 3).

给一个由正数组成的数组，找三个长度为k的不重叠的子数组，使得三个子数组的数字之和最大。

解法： DP，思路类似于123. Best Time to Buy and Sell Stock III，先分别从左和右两个方向求出每一个位置i之前的长度为k的元素和最大值，这样做的好处是之后想要得到某一位置的最大和时能马上知道。然后在用一个循环找出三段的最大和。

Java:

class Solution {

    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {

        int n = nums.length, maxsum = 0;

        int[] sum = new int[n+1], posLeft = new int[n], posRight = new int[n], ans = new int[3];

        for (int i = 0; i < n; i++) sum[i+1] = sum[i]+nums[i];

        // DP for starting index of the left max sum interval

        for (int i = k, tot = sum[k]-sum[0]; i < n; i++) {

            if (sum[i+1]-sum[i+1-k] > tot) {

                posLeft[i] = i+1-k;

                tot = sum[i+1]-sum[i+1-k];

            }

            else

                posLeft[i] = posLeft[i-1];

        }

        // DP for starting index of the right max sum interval

       // caution: the condition is ">= tot" for right interval, and "> tot" for left interval

        posRight[n-k] = n-k;

        for (int i = n-k-1, tot = sum[n]-sum[n-k]; i >= 0; i--) {

            if (sum[i+k]-sum[i] >= tot) {

                posRight[i] = i;

                tot = sum[i+k]-sum[i];

            }

            else

                posRight[i] = posRight[i+1];

        }

        // test all possible middle interval

        for (int i = k; i <= n-2*k; i++) {

            int l = posLeft[i-1], r = posRight[i+k];

            int tot = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]);

            if (tot > maxsum) {

                maxsum = tot;

                ans[0] = l; ans[1] = i; ans[2] = r;

            }

        }

        return ans;

    }

}

Python:　　

class Solution(object):

    def maxSumOfThreeSubarrays(self, nums, k):

        """

        :type nums: List[int]

        :type k: int

        :rtype: List[int]

        """

        n = len(nums)

        accu = [0]

        for num in nums:

            accu.append(accu[-1]+num)

        left_pos = [0] * n

        total = accu[k]-accu[0]

        for i in xrange(k, n):

            if accu[i+1]-accu[i+1-k] > total:

                left_pos[i] = i+1-k

                total = accu[i+1]-accu[i+1-k]

            else:

                left_pos[i] = left_pos[i-1]

        right_pos = [n-k] * n

        total = accu[n]-accu[n-k]

        for i in reversed(xrange(n-k)):

            if accu[i+k]-accu[i] > total:

                right_pos[i] = i;

                total = accu[i+k]-accu[i]

            else:

                right_pos[i] = right_pos[i+1]

        result, max_sum = [], 0

        for i in xrange(k, n-2*k+1):

            left, right = left_pos[i-1], right_pos[i+k]

            total = (accu[i+k]-accu[i]) + \

                    (accu[left+k]-accu[left]) + \

                    (accu[right+k]-accu[right])

            if total > max_sum:

                max_sum = total

                result = [left, i, right]

        return result

C++:

class Solution {

public:

    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {

        int n = nums.size(), maxsum = 0;

        vector<int> sum = {0}, posLeft(n, 0), posRight(n, n-k), ans(3, 0);

        for (int i:nums) sum.push_back(sum.back()+i);

       // DP for starting index of the left max sum interval

        for (int i = k, tot = sum[k]-sum[0]; i < n; i++) {

            if (sum[i+1]-sum[i+1-k] > tot) {

                posLeft[i] = i+1-k;

                tot = sum[i+1]-sum[i+1-k];

            }

            else

                posLeft[i] = posLeft[i-1];

        }

        // DP for starting index of the right max sum interval

        // caution: the condition is ">= tot" for right interval, and "> tot" for left interval

        for (int i = n-k-1, tot = sum[n]-sum[n-k]; i >= 0; i--) {

            if (sum[i+k]-sum[i] >= tot) {

                posRight[i] = i;

                tot = sum[i+k]-sum[i];

            }

            else

                posRight[i] = posRight[i+1];

        }

        // test all possible middle interval

        for (int i = k; i <= n-2*k; i++) {

            int l = posLeft[i-1], r = posRight[i+k];

            int tot = (sum[i+k]-sum[i]) + (sum[l+k]-sum[l]) + (sum[r+k]-sum[r]);

            if (tot > maxsum) {

                maxsum = tot;

                ans = {l, i, r};

            }

        }

        return ans;

    }

};

　　

　　

类似题目：

[LeetCode] 123. Best Time to Buy and Sell Stock III 买卖股票的最佳时间 III

All LeetCode Questions List 题目汇总

[LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和的相关教程结束。