题目描述

给定一个数组，数组中元素全部为正整数。
找到三个没有重叠的子数组，且子数组的长度均为K,使得这三个子数组的三个和加起来最大。
返回数组对应的下标，由于子数组长度已知，所以返回下标即可确定对应的子数组。
如果有重复的答案，那么返回字典序最小的。
即假如子数组长度为1 返回（0,3,5） 和(0,1,2) ，那么我们取(0,1,2)不取(0,3,5)。 因为012字典序小于035.

样例

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
子数组[1, 2], [2, 6], [7, 5] 的和最大，这时候有最优解。
对应下标(1,2)->0 (2,6)->3 (7,5)->5

算法

(动态规划) $O(n)$

采用i, i+1, … end表示从数组中下标i开始一直到末尾的这么一段
先考虑一个时候的情况,即从i开始一直到end这段区间内，选择一个子区间，连续长度为k的最大和是多少
那么可以写成：
F[i] = max(F[i+1], nums[i] + nums[i+1] + .... nums[i+k-1] )
含义：选用当前i开始的一段区间，或者从F[i+1]之后某个位置直接转移过来。

接下来考虑G[i],即从i开始一直到end这段区间内，选择两个子区间，连续长度为k的最大和是多少
G[i] = max(G[i+1], nums[i] + nums[i+1] + … + nums[i+k-1] + F[i+k])
含义：选用当前i开始的一段区间，由于是两个了，所以这时候再选需要从F[i+k]开始选择(注意这里是F[i+k]，因为我们选了第i->i+k-1这一段，所以能做的选择少了一个)，或者从G[i+1]之后某个位置直接转移过来。

接下来考虑T[i] 即从i开始一直到end这段区间内，选择三个子区间，连续长度为k的最大和是多少
T[i] = max(T[i+1], nums[i] + nums[i+1] + … + nums[i+k-1] + G[i+k])
含义：选用当前i开始的一段区间，由于是两个了，所以这时候再选需要从G[i+k]开始选择，或者从T[i+1]之后某个位置直接转移过来。

在实现动态规划时需要从后向前扫描，因为我们需要考虑的是字典序最小的，因此取等号的时候也要更新。

时间复杂度分析： 由于最多有三个，因此复杂度为O(n).

C++ 代码

class Solution {
public:
    // F[i] [i...end]  选一个最大为多少
    // G[i] [i...end]  选两个最大为多少 =max( G[i+1],F[i+k] + sum[i]+ ...+ sum[i+k-1])
    // T[i] [i...end]  选三个最大为多少 = max(G[i+1],G[i+k]+ sum[i] + ... + sum[i+k-1])

    vector<int> solution[20004][4];
    int F[20004][4];
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {

        vector<int> prefix(nums.size(),0);
        prefix[0] = nums[0];


        for (int i = 1;i<nums.size();++i)
            prefix[i] = prefix[i-1] + nums[i];

        int ret = 0;
        vector<int> best_solution;
        int size = nums.size();

        for (int count = 1; count <=3; count++){
            for (int i = size - count*k; i>=0; i--){
                F[i][count] = F[i+1][count];
                solution[i][count] = solution[i+1][count];

                int sum = prefix[i+k-1] - (i==0? 0 : prefix[i-1]) ;
                if (sum + F[i+k][count-1] >= F[i][count] ){
                    F[i][count] = sum + F[i+k][count-1];
                    solution[i][count].clear();
                    solution[i][count].push_back(i);
                    solution[i][count].insert(solution[i][count].end(),solution[i+k][count-1].begin(),solution[i+k][count-1].end());

                }
                if (count ==3 && F[i][count]>=ret)
                {
                    ret = F[i][count];
                    best_solution= solution[i][count];
                }
            }
        }

        return best_solution;
    }
};