Partition Array for Maximum Sum - Top down and bottom up DP

Array     C++     Dynamic Programming     Medium     Memoization    

Problem Statement:

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.

 

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]

Example 2:

Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83

Example 3:

Input: arr = [1], k = 1
Output: 1

 

Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length

Solution:

Top Down DP approach: dp[i] denotes answer for index i after considering all candidates for window sizes from 1 to K going forward. Final answer is dp[0].

 
class Solution {
    vector<int>dp;
public:
    int maxSum(vector<int>&A, int K, int N, int index)
    {
        if(index==N) return 0;
        if(dp[index]!=-1) return dp[index];
        int curMax = INT_MIN, res = INT_MIN;
        for(int i=index; i<index+K; i++)
        {
            if(i==N) break;
            curMax = max(curMax, A[i]);
            res = max(res, curMax * (i-index+1) + maxSum(A, K, N, i+1));
        }
        return dp[index] = res;
    }
    int maxSumAfterPartitioning(vector<int>& arr, int k) 
    {
        int n = arr.size();
        dp.resize(n,-1);
        return maxSum(arr,k,n,0);
    }
};
 

Bottom Up DP approach: dp[i] denotes answer for index i after considering all candidates for window sizes from 1 to K going backward. Final answer is dp[N-1].

 
class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) 
    {
        int n = arr.size();
        vector<int> dp(n,-1);
        for(int i=0; i<n; i++)
        {
            int curMax = INT_MIN;
            for(int j=i; j>i-k; j--)
            {
                if(j<0) break;
                curMax = max(curMax, arr[j]);
                int candidate = (j>0 ? dp[j-1] : 0) + (i-j+1) * curMax;
                dp[i] = max(dp[i], candidate);
            }
        }
        return dp.back();
    }
};
 

Both the approaches have $O(NK)$ time complexity and $O(N)$ space complexity. But top-down DP is slightly slower because of the load caused by the call stack.