今天的題目：
給你一串數字陣列跟數字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寫過
現在重寫一次
之前寫了一堆多餘的小雞巴東西
把他通通砍掉
捏