// Runtime: 4 ms, faster than 89.16% of Java online submissions for Partition Array for Maximum Sum.
class Solution {
    public int maxSumAfterPartitioning(int[] A, int K) {
        return part(A, K, 0, new int[A.length]);
    }

    public int part(int[] A, int K, int from, int[] dp) {
        if (from >= A.length) return 0;
        if (dp[from] != 0) return dp[from];

        int result = 0;

        int maxCount = Math.min(K, A.length - from);

        int[] max = new int[maxCount];
        max[0] = A[from];
        for (int i = 1; i < maxCount; i++)
            max[i] = Math.max(max[i-1], A[from + i]);

        for (int count = 1; count <= maxCount; count++) {
            int r  = max[count - 1] * count + part(A, K, from + count, dp);
            if (r > result) result = r;
        }

        dp[from] = result;
        return result;
    }
}