今天的题目：
给你一串数字阵列跟数字k
然后你可以让一个数字往扩张成k个
问你怎么让阵列加起来最大
做法：
每次都看一次k个数字的区间里面
跟之前算出来的数字加起来的最大的
所以要两层循环
一个跑全部数字
一个跑k的区间
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k)
{
int len = arr.size();
vector<int> paper(len , 0);
paper[0] = arr[0];
for(int i = 1 ; i < len ; i ++)
{
paper[i] = arr[i] + paper[i-1];
for(int j = 0 ; j < k ; j ++)
{
int pm = 0;
for(int g = i-j ; g <= i ; g ++)
{
pm = max(arr[g] , pm);
}
if(i-j-1 >= 0)
{
paper[i] = max(paper[i-j-1] + pm * (j+1) , paper[i]);
}
else if(i-j >= 0)
{
paper[i] = max( pm * (j+1) , paper[i]);
}
}
}
// for(int i = 0 ; i < len ; i ++)
// {
// printf("%d ",paper[i]);
// }
return paper[len-1];
}
};
这题我一段时间之前用c写过
现在重写一次
之前写了一堆多余的小鸡巴东西
把他通通砍掉
捏