[Leetcode]689.Maximum Sum of 3 Non-Overlapping Subarrays

时间:2021-08-18 17:58:34

链接:LeetCode689

给定数组?nums?由正整数组成,找到三个互不重叠的子数组的最大和。

每个子数组的长度为k,我们要使这3*k个项的和最大化。

返回每个区间起始索引的列表(索引从 0 开始)。如果有多个结果,返回字典序最小的一个。

示例:

输入: ([1,2,1,2,6,7,5,1], 2)
输出: ([0, 3, 5])
解释: 子数组 ([1, 2], [2, 6], [7, 5]) 对应的起始索引为 ([0, 3, 5])
我们也可以取 ([2, 1]), 但是结果 ([1, 3, 5]) 在字典序上更大。

相关标签:动态规划

又是一道明确是用动态规划解法后,便不难想出动态转移方程的题目。
下面考虑一般情况,也就是求解划分成(N)个不重叠数组的最大和。
假设到第(i)个元素为止,一共已经产生了(j)个不重叠数组,那么令$ dp[i][j] (表示这)j(个不重叠数组的最大和。 然后就要寻找状态转移方程。**对于第)i$个元素,分为两种情况,可取可不取。**
如果取,那就说明 (nums[i]) 是第(j)个子数组的最后一个元素,那么转移方程为:
[ dp[i][j] = dp[i-k][j-1] nums_{i-k 1:i} ]
也就是说,从(i-k 1)(i),这(k)个元素构成了第(j)个子数组,那我们只需要求到第(i-k)个元素为止,产生(j-1)个不重叠数组的最大和即可。
如果不取,那问题就变成了求到第(i-1)个元素为止,产生(j)个不重叠数组的最大和,那么转移方程为:
[ dp[i][j] = dp[i-1][j] ]
当然这题的难度还在于,需要你还原出最大和的情况下,所有子数组的起始元素下标,所以需要另外用一个数组保存一下每一步的最优下标。
同样,假设到第(i)个元素为止,一共已经产生了(j)个不重叠数组,用(path[i][j])表示第(j)个子数组的末尾元素下标。
那么按照上面的推断,如果取第(i)个元素,那么(path[i][j]=i);否则的话 (path[i][j]=path[i-1][j])。最后就是根据 path 数组还原答案了。

其代码如下:

python:

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        dp = [[0 for j in range(4)] for i in range(n 1)]
        path = [[0 for j in range(4)] for i in range(n 1)]
        cur = sum(nums[:k])
        sums = [cur]
        for i in range(k,n):
            cur  = nums[i] - nums[i-k]
            sums.append(cur)

        for i in range(1,n 1):
            for j in range(1,4):
                if i < j*k:
                    dp[i][j] = 0
                    continue
                dp[i][j] = dp[i-1][j]
                path[i][j] = path[i-1][j]
                if dp[i-k][j-1]   sums[i-k] > dp[i][j]:
                    dp[i][j] = dp[i-k][j-1]   sums[i-k]
                    path[i][j] = i-k

        res = []
        ind = n
        for j in reversed(range(1,4)):
            res.append(path[ind][j])
            ind = path[ind][j]
        res.reverse()
        return res

C :

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n 1,vector<int>(4,0));
        vector<vector<int>> path(n 1,vector<int>(4,0));
        int cur = accumulate(nums.begin(),nums.begin() k,0);
        vector<int> sums{cur};
        for(int i=k;i<n;  i){
            cur  = nums[i]-nums[i-k];
            sums.push_back(cur);
        }
        for(int i=1;i<n 1;  i){
            for(int j=1;j<4;  j){
                if(i<j*k){
                    continue;
                }
                dp[i][j] = dp[i-1][j];
                path[i][j] = path[i-1][j];
                if(dp[i-k][j-1] sums[i-k]>dp[i][j]){
                    dp[i][j] = dp[i-k][j-1] sums[i-k];
                    path[i][j] = i-k;
                }
            }
        }
        vector<int> res;
        int ind = n;
        for (int j=3;j>0;--j){
            res.insert(res.begin(),path[ind][j]);
            ind = path[ind][j];
        }
        return res;
    }
};

参考:[LeetCode 689]三个无重叠子数组的最大和