DAY 27 - Partition Array for Maximum Sum

Hey Guys! Nayan here and this is the 27th day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here.

DAY 27 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.

Examples:

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

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

Intuition:

The question can seem a little confusing at first, so let's try breaking it down to simple terms , get our objective and then proceed towards a possible solution.

• We are given an array arr. We have to divide it into mulitple partitions. Every partition can be of at most K size(which is given to us).

• Once we have divided the array into partitions, each element of that individual subarray gets replaced by the maximum element of that subarray.

• Hence as we can see in example 1: If we divide the array into 3 parts that are: [1,15,7] , [9] ,[2,5,10] our resultant subarrays after the given conditions are : [15,15,15] , [9] , [10,10,10].

• We add the total sum of this and get our output.

• To solve this problem we need to result out the maximum outcome possible.

Okay, So now that we have got our question straightened out let's think of a solution. The max partitions that we can do for k >= 1 will be size-1.

We can use a recursion function to find out all the possible partitions and their sums and hence we will be able to find out the maximum possible ans.

Let's not worry about complexity for now and think of forming up a solution.

Approach:

• Base case establishment: If our index reaches the end of array, we won't be able to do any more partitions and hence no sum can be added therefore after so we return 0.
• Now if we carefully se if we sum every time we form a partition that is gonna take too much time.
• What we would be better off doing is that, since every time we form a partition, we always calculate the max until that partition happens.
• Since it is going to replace all the elements inside it anyway, we can simply return length of the partition * max element we have found.
• We run a loop from index to end of size of array to form partitions and calculating the elements. Since we can't actually form a partition greater than size K, the max that we can go to is index + k. Unless index + k goes out of bounds, we go towards the size of array.
• We increment length by 1. We calculate the sum. Call it recursively for the next index.
• We take max function to get the maximum answer.
• Then we form a 1D dp array to memorize it by storing the maxAns we have found until that partition.

Code:

class Solution {
public:
    int helper(int index, int k, vector<int>& arr, vector<int> &dp){
        int n = arr.size();
        if(index == n) return 0;
        int len = 0;
        int maxi = INT_MIN;
        int maxAns = INT_MIN;
        if(dp[index] != -1){
            return dp[index];
        }

        for(int j = index; j < min(n, index + k); j++){
            len++;
            maxi = max(maxi, arr[j]);
            int sum = (len * maxi) + helper(j+1,k,arr,dp);
            maxAns = max(maxAns, sum);
        }
    return dp[index]  = maxAns;
    }
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n,-1);
        return helper(0,k,arr,dp);
    }

};

Complexity Analysis:

Time: O(N*k)
Space: O(N) + O(N). Extra space due to recursion stack space.

We can optimize the space complexity further using tabulation method.

Tabulation Approach:

• Reverse the indexes from the memoization approach.
• Establish the base cases.
• Follow the recursion relation for DP.

It can simply be done with these 3 steps.

int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n+1,0);
    //base case
        // dp[n] = 0;  not needed as already initialized as 0.

        for(int index = n-1; index >= 0; index--){
            int len = 0;
            int maxi = INT_MIN;
            int maxAns = INT_MIN;
            for(int j = index; j < min(n, index + k); j++){
                len++;
                maxi = max(maxi, arr[j]);
                int sum = (len * maxi) + dp[j+1];
                maxAns = max(maxAns, sum);
            }
            dp[index] = maxAns;
        }
        return dp[0];
        }

• Please note that sometimes while converting into DP code we might be going out of bounds for our recursive relation. Hence please increment the size of DP array accordingly. Here we added 1 more size to it to match indexing.

Complexity Analysis:

Time: O(N*k)
Space: O(N).

Thanks for reading. Feedback is highly appreciated.