---
description: Today 1 leet , tomorrow 頂天leet地
image: https://leetcode.com/static/images/LeetCode_Sharing.png
---
# Partition Array for Maximum Sum
[題目網址<i class="fa fa-link"></i>](https://leetcode.com/problems/partition-array-for-maximum-sum/)
## 題目敘述
Given an integer array `arr`, partition the array into (contiguous) subarrays of length **at most** `k`. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a **32-bit** integer.
:::spoiler **Example 1**

> **Input:** arr = [1,15,7,9,2,5,10], k = 3
> **Output:** 84
> **Explanation:** arr becomes
> [15,15,15,9,10,10,10]
:::

:::spoiler **Example 2**
> **Input:** arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
> **Output:** 83
:::

## 解題思維
此題如果用爆破的話效率極差，所以我使用DP
設dp[i]為在 **第i項的最大值**
規律為`dp[i] = dp[i-j] + max(A[i-1], ..., A[i-j]) * j`

## 程式碼

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int dp[501]={0},m;
        for(int i=1;i<=arr.size();i++)
        {
            m=0;
            for(int j=1;j<=k&&i-j>=0;j++)
            {
                m=max(m,arr[i-j]);
                dp[i]=max(dp[i-j]+m*j,dp[i]);
            }
        }
        return dp[arr.size()];
    }
};

$O(n)$

###### tags: `LeetCode` `Array` `Dynamic Programming`