Scale Engineer

Partition Array for Maximum Sum

Med
#0997Time: O(k^n). This is a loose upper bound, but the complexity is exponential. The recursion tree can branch up to `k` times at each level, and the depth can be up to `n`.Space: O(n), where n is the length of the array. This space is consumed by the recursion call stack, which can go as deep as n.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

A naive approach is to directly translate the problem's requirements into a recursive function. This function would explore every possible valid partition of the array. For any given starting point, it would try creating a partition of every possible length (from 1 to k), calculate the sum for that choice, and then recursively solve for the remainder of the array. The function would then return the best outcome among all these choices.

Algorithm

  • Define a recursive function solve(start_index).
  • Base Case: If start_index is at or beyond the end of the array, it means we have successfully partitioned the entire array. Return 0 as there are no more elements to sum.
  • Recursive Step:
    • Initialize a variable max_sum to 0 to keep track of the maximum possible sum starting from start_index.
    • Initialize current_max_in_partition to 0.
    • Loop with an index i from start_index to min(n-1, start_index + k - 1). This loop explores all possible end points for the first partition starting at start_index.
    • Inside the loop, update current_max_in_partition to be the maximum value seen so far in the partition arr[start_index...i].
    • Calculate the sum for this partition choice: (i - start_index + 1) * current_max_in_partition and add the result of the recursive call for the rest of the array, solve(i + 1).
    • Update max_sum with the maximum value found among all choices for i.
  • Return max_sum.
  • The initial call to start the process is solve(0).

Walkthrough

We can define a recursive function, say solve(i), which computes the maximum sum for the subarray starting at index i. To compute solve(i), we try all possible lengths for the first partition (from 1 to k). For each possible partition arr[i...j], we calculate its contribution, which is (j - i + 1) * max(arr[i...j]), and add it to the result of the recursive call on the rest of the array, solve(j + 1). We take the maximum over all possible choices for j.

This method is simple to conceptualize but suffers from a major drawback: it recomputes the solutions for the same subproblems multiple times. For instance, solve(5) might be called when partitioning from index 0, 1, 2, etc. This overlapping subproblem structure leads to an exponential number of calculations.

class Solution {    public int maxSumAfterPartitioning(int[] arr, int k) {        return solve(arr, k, 0);    }     private int solve(int[] arr, int k, int start) {        int n = arr.length;        if (start >= n) {            return 0;        }         int currentMax = 0;        int ans = 0;        int end = Math.min(n, start + k);        for (int i = start; i < end; i++) {            currentMax = Math.max(currentMax, arr[i]);            int partitionLength = i - start + 1;            ans = Math.max(ans, currentMax * partitionLength + solve(arr, k, i + 1));        }        return ans;    }}

Complexity

Time

O(k^n). This is a loose upper bound, but the complexity is exponential. The recursion tree can branch up to `k` times at each level, and the depth can be up to `n`.

Space

O(n), where n is the length of the array. This space is consumed by the recursion call stack, which can go as deep as n.

Trade-offs

Pros

  • Simple to write and understand as it directly models the problem's decision-making process.

Cons

  • Extremely inefficient due to a massive number of redundant computations for the same subproblems.

  • Guaranteed to result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized input due to its exponential nature.

Solutions

class Solution { public int maxSumAfterPartitioning ( int [] arr , int k ) { int n = arr . length ; int [] f = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; ++ i ) { int mx = 0 ; for ( int j = i ; j > Math . max ( 0 , i - k ); -- j ) { mx = Math . max ( mx , arr [ j - 1 ]); f [ i ] = Math . max ( f [ i ], f [ j - 1 ] + mx * ( i - j + 1 )); } } return f [ n ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem