Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

今天的題目：

給你一串數字陣列跟數字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寫過

現在重寫一次

之前寫了一堆多餘的小雞巴東西

把他通通砍掉

捏




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.45.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706933986.A.AAD.html
推 SecondRun: 大師
推 digua: 大師