Partition Array for Maximum Sum

Given an integer array arr[] and an integer k, partition the array into contiguous subarrays such that each subarray has a length of at most k. After partitioning, replace every element in each subarray with the maximum element present in that subarray. Compute the maximum possible sum of the array after performing this operation.

Input: arr[] = [1, 15, 7, 9, 2, 5, 10], k = 3
Output: 84
Explanation: One optimal partition is [1, 15, 7], [9], [2, 5, 10]. After replacing the elements of each subarray with the maximum value of that subarray, the array becomes [15, 15, 15, 9, 10, 10, 10]. Therefore, the total sum = 84.
Input: arr[] = [1], k = 1
Output: 1

Table of Content

Using Recursion – O(k^n) Time and O(n) Space
Using Dynamic Programming – O(n^2) Time and O(n) Space

Using Recursion – O(k^n) Time and O(n) Space

The idea is to try all possible partitions starting from the first index. For each index, we consider partitions of length 1 to k and compute the maximum value inside the current partition.
For every partition we calculate: partition_sum = maxElement × length_of_partition
Then recursively solve the remaining array and take the maximum result among all possibilities.

Steps to Implement

Start recursion from index 0.
For each position try partitions of length 1 to k.
Track the maximum element in the current partition.
Calculate the sum obtained from this partition.
Recursively compute the result for the remaining array.
Return the maximum sum among all partitions.

C++

using namespace std;

// Recursive function to compute maximum sum after partitioning
int maxSumAfterPartitionRec(vector<int>& arr, int i, int k) {
    int n = arr.size();

    if (i == n)
        return 0;

    int maxVal = 0;
    int ans = 0;

    for (int j = i; j < min(n, i + k); j++) {

        maxVal = max(maxVal, arr[j]);

        int len = j - i + 1;

        ans = max(ans,
                  maxVal * len + maxSumAfterPartitionRec(arr, j + 1, k));
    }

    return ans;
}

// Function to initiate recursion
int maxSumAfterPartition(vector<int>& arr, int k) {
    return maxSumAfterPartitionRec(arr, 0, k);
}

int main() {
    vector<int> arr = {1, 15, 7, 9, 2, 5, 10};
    int k = 3;

    cout << maxSumAfterPartition(arr, k) << endl;

    return 0;
}

Java

class GfG {

    // Recursive function to compute maximum sum after partitioning
    static int maxSumAfterPartitionRec(int[] arr, int i, int k) {
        int n = arr.length;

        if (i == n)
            return 0;

        int maxVal = 0;
        int ans = 0;

        for (int j = i; j < Math.min(n, i + k); j++) {

            maxVal = Math.max(maxVal, arr[j]);

            int len = j - i + 1;

            ans = Math.max(ans,
                           maxVal * len + maxSumAfterPartitionRec(arr, j + 1, k));
        }

        return ans;
    }

    // Function to initiate recursion
    static int maxSumAfterPartition(int[] arr, int k) {
        return maxSumAfterPartitionRec(arr, 0, k);
    }

    public static void main(String[] args) {
        int[] arr = {1, 15, 7, 9, 2, 5, 10};
        int k = 3;

        System.out.println(maxSumAfterPartition(arr, k));
    }
}

Python

# Recursive function to compute maximum sum after partitioning
def maxsumafterpartitionrec(arr, i, k):
    n = len(arr)

    if i == n:
        return 0

    maxval = 0
    ans = 0

    for j in range(i, min(n, i + k)):
        maxval = max(maxval, arr[j])
        length = j - i + 1
        ans = max(ans, maxval * length + maxsumafterpartitionrec(arr, j + 1, k))

    return ans

# Function to initiate recursion
def maxsumafterpartition(arr, k):
    return maxsumafterpartitionrec(arr, 0, k)

if __name__ == "__main__":
    arr = [1, 15, 7, 9, 2, 5, 10]
    k = 3
    print(maxsumafterpartition(arr, k))

using System;

class GFG {

    // Recursive function to compute maximum sum after
    // partitioning
    static int maxSumAfterPartitionRec(int[] arr, int i,
                                       int k)
    {
        int n = arr.Length;

        if (i == n)
            return 0;

        int maxVal = 0;
        int ans = 0;

        for (int j = i; j < Math.Min(n, i + k); j++) {

            maxVal = Math.Max(maxVal, arr[j]);

            int len = j - i + 1;

            ans = Math.Max(ans,
                           maxVal * len
                               + maxSumAfterPartitionRec(
                                   arr, j + 1, k));
        }

        return ans;
    }

    // Function to initiate recursion
    static int maxSumAfterPartition(int[] arr, int k)
    {
        return maxSumAfterPartitionRec(arr, 0, k);
    }

    static void Main()
    {
        int[] arr = { 1, 15, 7, 9, 2, 5, 10 };
        int k = 3;

        Console.WriteLine(maxSumAfterPartition(arr, k));
    }
}

JavaScript

// Recursive function to compute maximum sum after partitioning
function maxSumAfterPartitionRec(arr, i, k) {
    const n = arr.length;

    if (i === n)
        return 0;

    let maxVal = 0;
    let ans = 0;

    for (let j = i; j < Math.min(n, i + k); j++) {

        maxVal = Math.max(maxVal, arr[j]);

        let len = j - i + 1;

        ans = Math.max(ans, maxVal * len + maxSumAfterPartitionRec(arr, j + 1, k));
    }

    return ans;
}

// Function to initiate recursion
function maxSumAfterPartition(arr, k) {
    return maxSumAfterPartitionRec(arr, 0, k);
}

// driver code
const arr = [1, 15, 7, 9, 2, 5, 10];
const k = 3;
console.log(maxSumAfterPartition(arr, k));

Output

Using Dynamic Programming – O(n^2) Time and O(n) Space

The recursive solution recalculates many subproblems multiple times. This can be optimized using Dynamic Programming. Define a DP array dp[] where dp[i] represents the maximum sum achievable using the first i elements. For each position i, consider partitions ending at index i - 1 with size at most k. While expanding the partition backwards, maintain the maximum element in the partition and update the best possible value