# 1043. Partition Array for Maximum Sum
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/partition-array-for-maximum-sum/
## 思路
和[1105. Filling Bookcase Shelves](https://hackmd.io/SStKMDA2S2OdA5X256a7KA)一样
可以直接去看1105的思路
这里我们把j当成上一个subarray的最后一个元素 那么num[j+1]就是和num[i]在一个subarray里的第一个元素
## Code

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] num = new int[n+1];
        for(int i=1; i<=n; i++) num[i] = arr[i-1];
        
        int[] dp = new int[n+1];
        for(int i=1; i<=n; i++){
            int max = num[i];
            for(int j=i-1; j>=0; j--){
                max = Math.max(max, num[j+1]);
                if(i-j<=k){
                    dp[i] = Math.max(dp[i], max*(i-j)+dp[j]);
                }
                else break;
            }
        }
        return dp[n];
    }
}