# Partition Array for Maximum Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-array-for-maximum-sum)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-for-maximum-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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
## Brute-Force Recursion
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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)`.

## Top-Down Dynamic Programming with Memoization
The brute-force recursive approach is slow because it repeatedly solves the same subproblems. We can significantly improve performance by storing the results of these subproblems in a cache or memoization table. This technique, where we use a recursive structure but store results to avoid re-computation, is known as memoization or top-down dynamic programming.
**Time:** O(n * k). There are `n` possible states for `start_index` (0 to `n-1`). Each state is computed only once. The computation for each state involves a loop that runs at most `k` times. · **Space:** O(n). This includes O(n) for the memoization array and O(n) for the recursion stack depth.
**Pros:** Drastically improves performance over brute-force by eliminating redundant computations.; Maintains the logical clarity and readability of the recursive structure.
**Cons:** Can have a slightly higher constant overhead compared to the iterative bottom-up approach due to function call overhead.; In languages with limited recursion depth, it could theoretically lead to a stack overflow for very large `n` (though not an issue with the given constraints).
### Explanation
The structure of the recursive solution remains the same as the brute-force approach. We still have a function `solve(i)` that finds the maximum sum for the suffix `arr[i:]`. The key difference is that before computing `solve(i)`, we check if the result is already stored in our memoization array (e.g., `memo`). If it is, we return the stored value immediately. Otherwise, we compute the result as before, and just before returning, we store it in `memo[i]` for future use. This simple addition ensures that each subproblem `solve(i)` is computed only once, dramatically reducing the time complexity.

```java
import java.util.Arrays;

class Solution {
    int[] memo;
    int n;
    int k;
    int[] arr;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        this.n = arr.length;
        this.k = k;
        this.arr = arr;
        this.memo = new int[n];
        Arrays.fill(memo, -1); // -1 indicates not computed
        return solve(0);
    }

    private int solve(int start) {
        if (start >= n) {
            return 0;
        }
        if (memo[start] != -1) {
            return memo[start];
        }

        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(i + 1));
        }
        return memo[start] = ans;
    }
}
```
### Algorithm
- Create a memoization array `memo` of size `n` and initialize it with a sentinel value (e.g., -1) to indicate that a subproblem has not been solved yet.
- Use the same recursive function `solve(start_index)` as in the brute-force approach.
- **Memoization Check**: At the beginning of the function, check if `memo[start_index]` has been computed (i.e., not equal to -1). If so, return the stored value immediately.
- **Compute and Store**: If the value is not in the memo table, compute it using the same recursive logic as before. Before returning the result, store it in `memo[start_index]`.
- The initial call is `solve(0)`.

## Bottom-Up Dynamic Programming
An alternative to the top-down (memoized recursion) approach is the bottom-up (or iterative) dynamic programming approach. Instead of starting from the main problem and breaking it down, we solve the problem by starting from the smallest subproblems and iteratively building up to the final solution. This approach avoids recursion and often has slightly better performance due to lower overhead.
**Time:** O(n * k). The outer loop runs `n` times, and the inner loop runs at most `k` times for each outer iteration. · **Space:** O(n) for the DP array. This can be optimized to O(k) since each `dp[i]` only depends on the previous `k` values.
**Pros:** Generally the most efficient solution in practice due to its iterative nature and lack of recursion overhead.; Avoids any risk of stack overflow, making it robust for all valid inputs.
**Cons:** The logic might be slightly less direct to formulate compared to the recursive top-down approach for some developers.; The standard implementation uses O(n) space, though it can be optimized.
### Explanation
We use a DP array, say `dp`, of size `n+1`. `dp[i]` will store the maximum sum we can get for the prefix of the array of length `i` (i.e., `arr[0...i-1]`).

The base case is `dp[0] = 0`, representing an empty prefix with a sum of 0.

We then iterate from `i = 1` to `n` to compute `dp[i]`. To find `dp[i]`, we look back and consider all possible last partitions that could end at index `i-1`. A last partition can have a length `j` from 1 to `k`. If the last partition has length `j`, it starts at index `i-j`. The sum for this configuration would be `dp[i-j]` (the max sum for the array before this partition) plus the value of this new partition. The value of the partition `arr[i-j...i-1]` is `j * max(arr[i-j...i-1])`. We take the maximum over all possible lengths `j`.

This approach can be further optimized in space. Notice that to compute `dp[i]`, we only need the previous `k` values (`dp[i-1], ..., dp[i-k]`). This means we could reduce the space complexity from `O(n)` to `O(k)` by using a circular array.

```java
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1]; // dp[i] = max sum for arr[0...i-1]

        for (int i = 1; i <= n; i++) {
            int maxInPartition = 0;
            // Iterate on the length 'j' of the last partition ending at i-1
            for (int j = 1; j <= k && i - j >= 0; j++) {
                // The current last element of the partition being considered is arr[i-j]
                maxInPartition = Math.max(maxInPartition, arr[i - j]);
                // The sum is the best sum before this partition (dp[i-j]) 
                // plus the value of this partition (maxInPartition * j)
                dp[i] = Math.max(dp[i], dp[i - j] + maxInPartition * j);
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n+1`, where `dp[i]` will store the maximum sum for the prefix `arr[0...i-1]`.
- Initialize `dp[0] = 0`, as the sum of an empty prefix is 0.
- Iterate with `i` from 1 to `n` to compute all `dp` values from `dp[1]` to `dp[n]`.
- To compute `dp[i]`, we consider all possible last partitions that end at index `i-1`. We can do this by iterating on the length of the last partition, say `j`, from 1 to `k`.
    - The last partition is `arr[i-j...i-1]`. This is only valid if `i-j >= 0`.
    - We need the maximum element within this partition. We can find this efficiently by keeping a running maximum as we iterate `j`.
    - The total sum for this choice of partition is `dp[i-j]` (the optimal sum for the prefix before this partition) plus `maxInPartition * j` (the value of this last partition).
    - Update `dp[i]` to be the maximum value found across all valid partition lengths `j`.
- The final answer is `dp[n]`, which represents the maximum sum for the entire array `arr[0...n-1]`.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Solution { public: int maxSumAfterPartitioning ( vector < int >& arr , int k ) { int n = arr . size (); int f [ n + 1 ]; memset ( f , 0 , sizeof ( f )); for ( int i = 1 ; i <= n ; ++ i ) { int mx = 0 ; for ( int j = i ; j > max ( 0 , i - k ); -- j ) { mx = max ( mx , arr [ j - 1 ]); f [ i ] = max ( f [ i ], f [ j - 1 ] + mx * ( i - j + 1 )); } } return f [ n ]; } };
```

### Python

```python
class Solution : def maxSumAfterPartitioning ( self , arr : List [ int ], k : int ) -> int : n = len ( arr ) f = [ 0 ] * ( n + 1 ) for i in range ( 1 , n + 1 ): mx = 0 for j in range ( i , max ( 0 , i - k ), - 1 ): mx = max ( mx , arr [ j - 1 ]) f [ i ] = max ( f [ i ], f [ j - 1 ] + mx * ( i - j + 1 )) return f [ n ]
```