1043. Partition Array for Maximum Sum

 一刷 06/2022

Version #1 DP

The space can be optimized to O(K) by taking residual of K using rotation dp method, but we don't implement it here

Time - array length N -> O(NK)

Space O(N)

Runtime: 6 ms, faster than 89.24% of Java online submissions for Partition Array for Maximum Sum.

Memory Usage: 43.5 MB, less than 10.47% of Java online submissions for Partition Array for Maximum Sum.

class Solution {

    public int maxSumAfterPartitioning(int[] arr, int k) {

        // The max sum of previous i numbers

        // base case: dp[0] = 0

        // recursive equation: dp[j] = max{dp[i] + max number between [i, j) * (j - i)

        int[] dp = new int[arr.length + 1];

        for (int i = 1; i <= arr.length; i++) {

            // nums[i - 1]

            dp[i] = Integer.MIN_VALUE;

            int maxNum = Integer.MIN_VALUE;

            for (int len = 1; len <= k && len <= i; len++) {

                // k = 1, len = 1

                // nums[i - 1] to nums[i - len]

                maxNum = Math.max(maxNum, arr[i - len]);

                dp[i] = Math.max(dp[i], dp[i - len] + maxNum * len);

            }

        }

        return dp[arr.length];

    }

}