Partition Array for Maximum Sum | Front Partition : DP 54

Problem Statement: Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has its values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Examples
Example 1:
Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: The partition will be the following to get the largest sum:
 [1, 15, 7 | 9 | 2, 5, 10]. 
After replacing the elements of each subarray with its maximum, the array will look like this:[15,15,15,9,10,10,10] and the sum will be 84.
Example 2:
Input: arr[] = [1], k = 1
Output: 1
Explanation: only one partition is possible 
like this: [1] and the sum will be 1.
Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Recursive approach Memoization approach Tabulation Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Recursive Approach
Algorithm / Intuition

In order to solve this problem, we need to partition the given array in such a way that the length of every substring does not exceed k. For example, if the array, [1,15,7,9,2,5,10], is given and the value of k is 3, one of the valid partitions will be [1,15, | 7,9,2, | 5,10].  In this case, the length of each substring is smaller or equal to k.
Now, after making such partitions following the above way, we need to change the elements of each substring with its maximum element. Then we will calculate the sum of the whole array. If we apply this to the above array, it will be like  [15,15, | 9,9,9, | 10,10] and the sum will be 77.

Here, in the question, it is clearly mentioned that we have to do the partition in such a way that the sum of the array becomes the maximum possible.

Intuition:

This problem is similar to the problem Palindrome Partitioning – II. We are also going to solve this problem using the front partition. In the front partition technique, we generally start checking from the starting index and check if we can make a partition after that particular index.

We have found the right approach so far. Now, let us quickly discuss the rules to write the recurrence to solve this problem:

  1. Express everything(i.e. the given array) in terms of the index.
  2. Try all partitions.
  3. Return the best possible answer of all partitions (i.e. the answers that come after dividing the problem into subproblems and solving them recursively).
    Derive the base case as well.

To explain the rules, we are considering example 1 i.e. arr = [1,15,7,9,2,5,10] and k = 3.

Express everything(i.e. the given array) in terms of the index:

We are given an array and so it is easy to express the array in terms of the index. Now, following the front partition rules we will place the pointer ind to index 0 i.e. the first index. The function will look like the following:

Try all partitions:

f(ind) actually considers the subarray starting from index ind up to the end index and returns the maximum possible sum by making partitions in that particular subarray. For example, if the given array is [1,15,7,9,2,5,10], f(2) considers the subarray [7,9,2,5,10](following 0-based indexing).
As we have figured out the logic for marking the pointer, ind, we will move to the partitioning loop. We can simply write a for loop(say j) starting from ind to ind+k-1(k = given subarray size) as it is clearly mentioned that the length of a partition can be at most k.  The problem is being broken in the following manner(considering the specified example):

Note: It may happen that the limit ind+k-1 exceeds the length of the array. That is why we will take the limit of j as min(n, ind+k-1) where n = size of the array. This will avoid the runtime error.
Base case: When the value of ind becomes equal to n(n = size of the array), we can say there are no elements left to be considered. So, when (ind == n) the function will return 0.

Return the best possible answer of all partitions:

Observation: How to calculate the answer

It is clearly stated in the question that after making a partition, we have to replace all the elements of the subarray with the maximum element of that subarray. So, we will follow the same.Inside the partitioning loop, after making a partition at j, all the elements of the subarray arr[ind….j] will turn into the maximum element of that subarray i.e. maximum(arr[ind….j]). Therefore, the sum of the subarray will be (maximum element * length of the subarray). Consider the illustration below:

So, the answer will be the summation of the sum of the left subarray and the answer returned by the subproblem starting from index j+1 i.e. Sum =  (maximum element * length of the subarray) + f(j+1).

Now, calculating all possible sums, we will consider the maximum one.

Note: If you wish to see the dry run of the above approach, you can watch the video attached to this article.

Approach

The recursive algorithm steps are as follows:

  1. Convert the problem to a recursive function marked by the pointer ind.
  2. Use a loop to check all possible partitions of the array and calculate the maximum sum we can achieve.
  3. Return the maximum possible sum.

Base case: When the value of ind becomes equal to n(n = size of the array), we can say there are no elements left to be considered. So, when (ind == n) the function will return 0.

Code

#include <bits/stdc++.h>
using namespace std;

// Recursive function to find the maximum sum after partitioning.
int maxSumAfterPartitioning(vector<int>& num, int k) {
    int n = num.size();

    // Base case: If the current index is equal to the size of the array, return 0.
    if (ind == n) return 0;

    int len = 0;
    int maxi = INT_MIN;
    int maxAns = INT_MIN;

    // Loop through the array starting from the current index.
    for (int j = ind; j < min(ind + k, n); j++) {
        len++;
        maxi = max(maxi, num[j]);
        int sum = len * maxi + maxSumAfterPartitioning(j + 1, num, k);
        maxAns = max(maxAns, sum);
    }
    return maxAns;
}

int main() {
    vector<int> num = {1, 15, 7, 9, 2, 5, 10};
    int k = 3;
    int maxSum = maxSumAfterPartitioning(num, k);
    cout << "The maximum sum is: " << maxSum << "\n";
    return 0;
}



public class MaxSumAfterPartitioning {
    static int f(int ind, int[] num, int k) {
        int n = num.length;
        // Base case:
        if (ind == n) return 0;

        int len = 0;
        int maxi = Integer.MIN_VALUE;
        int maxAns = Integer.MIN_VALUE;
        
        // Iterate through the next 'k' elements or remaining elements if less than 'k'.
        for (int j = ind; j < Math.min(ind + k, n); j++) {
            len++;
            maxi = Math.max(maxi, num[j]);
            int sum = len * maxi + f(j + 1, num, k);
            maxAns = Math.max(maxAns, sum);
        }
        return maxAns;
    }

    static int maxSumAfterPartitioning(int[] num, int k) {
        return f(0, num, k);
    }

    public static void main(String[] args) {
        int[] num = {1, 15, 7, 9, 2, 5, 10};
        int k = 3;
        int maxSum = maxSumAfterPartitioning(num, k);
        System.out.println("The maximum sum is: " + maxSum);
    }
}




def max_sum_after_partitioning(num, k):
    n = len(num)
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        max_val = 0
        for j in range(1, min(i, k) + 1):
            max_val = max(max_val, num[i - j])
            dp[i] = max(dp[i], dp[i - j] + max_val * j)

    return dp[n]

if __name__ == "__main__":
    num = [1, 15, 7, 9, 2, 5, 10]
    k = 3
    max_sum = max_sum_after_partitioning(num, k)
    print("The maximum sum is:", max_sum)



// Function to find the maximum sum after partitioning an array
function maxSumAfterPartitioning(num, k) {
    const n = num.length;

    // Function f to recursively calculate the maximum sum
    function f(ind) {
        // Base case: If ind reaches the end of the array, return 0
        if (ind === n) return 0;

        let len = 0;
        let maxi = -Infinity;
        let maxAns = -Infinity;

        // Loop through the array from index 'ind' up to 'ind + k' or 'n', whichever is smaller
        for (let j = ind; j < Math.min(ind + k, n); j++) {
            len++;
            maxi = Math.max(maxi, num[j]);

            // Calculate the sum for the current partition and recursive call
            const sum = len * maxi + f(j + 1);
            maxAns = Math.max(maxAns, sum);
        }

        return maxAns;
    }

    // Call the recursive function with initial index 0
    return f(0);
}

// Main function
function main() {
    const num = [1, 15, 7, 9, 2, 5, 10];
    const k = 3;
    const maxSum = maxSumAfterPartitioning(num, k);
    console.log("The maximum sum is:", maxSum);
}

// Call the main function
main();

The maximum sum is: 84 (For example 1)

Complexity Analysis

Time Complexity: Exponential

Memoization Approach
Algorithm / Intuition

Steps to memoize the recursive solution:

  1. Create a 1D dp array of size [n]. ind can range from 0 to n-1. So we take the size n.
  2. We initialize the dp array to -1.
  3. Whenever we want to find the answer to a particular parameter (say f(ind)), we first check whether the answer is already calculated using the dp array(i.e dp[ind] != -1 ). If yes, simply return the value from the dp array.
  4. If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind] to the solution we get.
Code


#include <bits/stdc++.h>
using namespace std;

// Recursive function to find the maximum sum after partitioning.
int f(int ind, vector<int> &num, int k, vector<int> &dp) {
    int n = num.size();

    // Base case: If the current index is equal to the size of the array, return 0.
    if (ind == n) return 0;

    // If the result for this index is already computed, return it from dp array.
    if (dp[ind] != -1) return dp[ind];

    int len = 0;
    int maxi = INT_MIN;
    int maxAns = INT_MIN;

    // Loop through the array starting from the current index.
    for (int j = ind; j < min(ind + k, n); j++) {
        len++;
        maxi = max(maxi, num[j]);
        int sum = len * maxi + f(j + 1, num, k, dp);
        maxAns = max(maxAns, sum);
    }

    // Store the computed result in the dp array and return it.
    return dp[ind] = maxAns;
}

int maxSumAfterPartitioning(vector<int>& num, int k) {
    int n = num.size();
    vector<int> dp(n, -1);
    return f(0, num, k, dp);
}

int main() {
    vector<int> num = {1, 15, 7, 9, 2, 5, 10};
    int k = 3;
    int maxSum = maxSumAfterPartitioning(num, k);
    cout << "The maximum sum is: " << maxSum << "\n";
    return 0;
}




public class MaxSumAfterPartitioning {
    static int f(int ind, int[] num, int k, int[] dp) {
        int n = num.length;
        // Base case:
        if (ind == n) return 0;

        if (dp[ind] != -1) return dp[ind];
        int len = 0;
        int maxi = Integer.MIN_VALUE;
        int maxAns = Integer.MIN_VALUE;
        
        // Iterate through the next 'k' elements or remaining elements if less than 'k'.
        for (int j = ind; j < Math.min(ind + k, n); j++) {
            len++;
            maxi = Math.max(maxi, num[j]);
            int sum = len * maxi + f(j + 1, num, k, dp);
            maxAns = Math.max(maxAns, sum);
        }
        return dp[ind] = maxAns;
    }

    static int maxSumAfterPartitioning(int[] num, int k) {
        int n = num.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return f(0, num, k, dp);
    }

    public static void main(String[] args) {
        int[] num = {1, 15, 7, 9, 2, 5, 10};
        int k = 3;
        int maxSum = maxSumAfterPartitioning(num, k);
        System.out.println("The maximum sum is: " + maxSum);
    }
}




def max_sum_after_partitioning(num, k):
    n = len(num)
    dp = [-1] * n

    def f(ind):
        # Base case:
        if ind == n:
            return 0

        if dp[ind] != -1:
            return dp[ind]

        len_val = 0
        max_val = float('-inf')
        max_ans = float('-inf')

        for j in range(ind, min(ind + k, n)):
            len_val += 1
            max_val = max(max_val, num[j])
            summation = len_val * max_val + f(j + 1)
            max_ans = max(max_ans, summation)

        dp[ind] = max_ans
        return dp[ind]

    return f(0)

if __name__ == "__main__":
    num = [1, 15, 7, 9, 2, 5, 10]
    k = 3
    max_sum = max_sum_after_partitioning(num, k)
    print("The maximum sum is:", max_sum)




// Function to find the maximum sum after partitioning an array
function maxSumAfterPartitioning(num, k) {
    const n = num.length;

    // Create a memoization table dp to store calculated values
    const dp = new Array(n).fill(-1);

    // Function f to recursively calculate the maximum sum
    function f(ind) {
        // Base case: If ind reaches the end of the array, return 0
        if (ind === n) return 0;

        // Check if the result for this index is already computed
        if (dp[ind] !== -1) return dp[ind];

        let len = 0;
        let maxi = -Infinity;
        let maxAns = -Infinity;

        // Loop through the array from index 'ind' up to 'ind + k' or 'n', whichever is smaller
        for (let j = ind; j < Math.min(ind + k, n); j++) {
            len++;
            maxi = Math.max(maxi, num[j]);

            // Calculate the sum for the current partition and recursive call
            const sum = len * maxi + f(j + 1);
            maxAns = Math.max(maxAns, sum);
        }

        // Store the result in the memoization table
        dp[ind] = maxAns;
        return maxAns;
    }

    // Call the recursive function with initial index 0
    return f(0);
}

// Main function
function main() {
    const num = [1, 15, 7, 9, 2, 5, 10];
    const k = 3;
    const maxSum = maxSumAfterPartitioning(num, k);
    console.log("The maximum sum is:", maxSum);
}

// Call the main function
main();

The maximum sum is: 84 (For example 1)

Complexity Analysis

Time Complexity: O(N*k)
Reason: There are a total of N states and for each state, we are running a loop from 0 to k.

Space Complexity: O(N) + Auxiliary stack space O(N)
Reason: First O(N) for the dp array we are using.

Tabulation Approach
Algorithm / Intuition

Tabulation:

  1. First of all, we handle the base case. If (ind == n) we return 0. To cover this case we can initialize the entire dp array with 0.
    Here, as we are checking dp[j+1]  every time, the function will give a runtime error if j = n-1. To avoid this, we will take the array size as n+1 instead of n.
  2. Next, memoization is a top-down approach, whereas tabulation is bottom-up. Our changing parameter ind will change in opposite directions, i.e ind will change from n-1→0.
  3. Next, we copy down the recursive logic(recurrence) inside the loop.
Code

#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum sum after partitioning the array.
int maxSumAfterPartitioning(vector<int>& num, int k) {
    int n = num.size();
    
    // Create a DP array to store the maximum sum.
    vector<int> dp(n + 1, 0);
    
    // Iterate through the array from right to left.
    for (int ind = n - 1; ind >= 0; ind--) {
        int len = 0;
        int maxi = INT_MIN;
        int maxAns = INT_MIN;
        
        // Loop through the next k elements (or remaining elements if k is smaller).
        for (int j = ind; j < min(ind + k, n); j++) {
            len++;
            maxi = max(maxi, num[j]);
            int sum = len * maxi + dp[j + 1];
            maxAns = max(maxAns, sum);
        }
        
        // Store the computed maximum sum in the DP array.
        dp[ind] = maxAns;
    }
    
    // The maximum sum after partitioning the entire array is stored in dp[0].
    return dp[0];
}

int main() {
    vector<int> num = {1, 15, 7, 9, 2, 5, 10};
    int k = 3;
    int maxSum = maxSumAfterPartitioning(num, k);
    cout << "The maximum sum is: " << maxSum << "\n";
    return 0;
}



public class MaxSumAfterPartitioning {
    static int maxSumAfterPartitioning(int[] num, int k) {
        int n = num.length;
        int[] dp = new int[n + 1];
        
        // Traverse the input array from right to left
        for (int ind = n - 1; ind >= 0; ind--) {
            int len = 0;
            int maxi = Integer.MIN_VALUE;
            int maxAns = Integer.MIN_VALUE;
            
            // Iterate through the next 'k' elements or remaining elements if less than 'k'.
            for (int j = ind; j < Math.min(ind + k, n); j++) {
                len++;
                maxi = Math.max(maxi, num[j]);
                int sum = len * maxi + dp[j + 1];
                maxAns = Math.max(maxAns, sum);
            }
            dp[ind] = maxAns;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        int[] num = {1, 15, 7, 9, 2, 5, 10};
        int k = 3;
        int maxSum = maxSumAfterPartitioning(num, k);
        System.out.println("The maximum sum is: " + maxSum);
    }
}



def max_sum_after_partitioning(num, k):
    n = len(num)
    dp = [0] * (n + 1)

    for ind in range(n - 1, -1, -1):
        len_val = 0
        max_val = float('-inf')
        max_ans = float('-inf')

        for j in range(ind, min(ind + k, n)):
            len_val += 1
            max_val = max(max_val, num[j])
            summation = len_val * max_val + dp[j + 1]
            max_ans = max(max_ans, summation)

        dp[ind] = max_ans

    return dp[0]

if __name__ == "__main__":
    num = [1, 15, 7, 9, 2, 5, 10]
    k = 3
    max_sum = max_sum_after_partitioning(num, k)
    print("The maximum sum is:", max_sum)




/// Function to find the maximum sum after partitioning an array
function maxSumAfterPartitioning(num, k) {
    const n = num.length;

    // Create an array dp to store the maximum sum for each index
    const dp = new Array(n + 1).fill(0);

    // Loop through the array from the end to the beginning
    for (let ind = n - 1; ind >= 0; ind--) {
        let len = 0;
        let maxi = -Infinity;
        let maxAns = -Infinity;

        // Loop through elements from 'ind' to 'ind + k' or 'n', whichever is smaller
        for (let j = ind; j < Math.min(ind + k, n); j++) {
            len++;
            maxi = Math.max(maxi, num[j]);

            // Calculate the sum for the current partition and add it to the value in dp for the next index
            const sum = len * maxi + dp[j + 1];
            maxAns = Math.max(maxAns, sum);
        }

        // Store the maximum sum in dp for the current index
        dp[ind] = maxAns;
    }

    // The result is stored in dp[0]
    return dp[0];
}

// Main function
function main() {
    const num = [1, 15, 7, 9, 2, 5, 10];
    const k = 3;
    const maxSum = maxSumAfterPartitioning(num, k);
    console.log("The maximum sum is:", maxSum);
}

// Call the main function
main();


The maximum sum is: 84 (For example 1)

Complexity Analysis

Time Complexity: O(N*k)
Reason: There are a total of N states and for each state, we are running a loop from 0 to k.

Space Complexity: O(N)
Reason: O(N) for the dp array we are using.

Video Explanation

Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this articleIf you want to suggest any improvement/correction in this article please mail us at [email protected]