【力扣·每日一题】689. 三个无重叠子数组的最大和 (C++ 前缀和优化dp 保存路径)

【力扣·每日一题】689. 三个无重叠子数组的最大和 (C++ 前缀和优化dp 保存路径)

linkk

题意

思路

dp转移，前缀和优化。
多加一个 p r e pre pre的数组存储路径。

首先，数组的长度为 2 e 4 2e4 2e4，暴力肯定是不可行的。
考虑用 d p dp dp去转移。
设 d p [ i ] [ j ] dp[i][j] dp[i][j]表示从前 i i i个数分为 j j j组得到的最大价值。
对于第 i i i个数有两种选择：属于第 j j j组或属于第 j − 1 j-1 j−1组。
对相应的转移进行判断就好了。

代码

class Solution {
public:
    vector maxSumOfThreeSubarrays(vector& nums, int k) {
        int n=nums.size();
        int sum[n],ans=0,dp[n][5],pre[n][5];
        memset(sum,0,sizeof sum);
        memset(dp,0,sizeof dp);
        for(int i=0;ires;
        int x=pre[n-1][3];
        res.push_back(x-k+1);
        for(int i=2;i>0;i--){
            x=pre[x-k][i];
            res.push_back(x-k+1);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};