题意
思路
dp转移，前缀和优化。
多加一个p r e的数组存储路径。
首先，数组的长度为2 e 4，暴力肯定是不可行的。
考虑用d p去转移。
设d p [ i ] [ j ]表示从前i个数分为j组得到的最大价值。
对于第i个数有两种选择：属于第j jj组或属于第j − 1组。
对相应的转移进行判断就好了。
代码
class Solution { public: vector<int> maxSumOfThreeSubarrays(vector<int>& 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;i<k;i++){ ans=ans+nums[i]; } sum[k-1]=ans; for(int i=k;i<n;i++){ ans=ans+nums[i]-nums[i-k]; sum[i]=ans; } dp[k-1][1]=sum[k-1];pre[k-1][1]=k-1; for(int i=k;i<n;i++){ for(int j=1;j<=3;j++){ dp[i][j]=dp[i-1][j];//第i个不选 pre[i][j]=pre[i-1][j]; if(dp[i][j]<dp[i-k][j-1]+sum[i]){ dp[i][j]=dp[i-k][j-1]+sum[i]; pre[i][j]=i; } } } vector<int>res; 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; } };
