# LeetCode 1043: Partition Array for Maximum Sum

## Problem Restatement

We are given an integer array `arr` and an integer `k`.

We can partition `arr` into contiguous subarrays of length at most `k`.

After partitioning, each element in a subarray is replaced by the maximum value of that subarray.

We need to return the maximum sum of the resulting array.

The official constraints state that `1 <= k <= arr.length <= 500` and `0 <= arr[i] <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr` and integer `k` |
| Output | Maximum possible sum after optimal partitioning |

Function shape:

```python
def maxSumAfterPartitioning(arr: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [1, 15, 7, 9, 2, 5, 10]
k = 3
```

Partition: `[1, 15, 7]`, `[9, 2, 5]`, `[10]`.

After: `[15, 15, 15, 9, 9, 9, 10]`. Sum = `82`.

Answer:

```python
84
```

One strong partition is `[1,15,7]`, `[9]`, `[2,5,10]`. Its value is `15*3 + 9*1 + 10*3 = 84`.

`[1,15]`, `[7,9,2]`, `[5,10]` → `15*2 + 9*3 + 10*2 = 30 + 27 + 20 = 77`. Worse.

`[1,15,7]`, `[9]`, `[2,5,10]` → `45 + 9 + 30 = 84`.

Answer: `84`.

## Key Insight

Let `dp[i]` = maximum sum for the prefix `arr[:i]`.

For each position `i`, try all partition lengths `l` from `1` to `k`:

```python
dp[i] = max(dp[i - l] + max(arr[i-l:i]) * l)
```

## Correctness

For each ending position `i` and partition length `l`, the last partition covers `arr[i-l:i]`. All elements in this partition become the maximum of that partition. Adding `dp[i-l]` gives the best result for the prefix before the partition.

The maximum over all valid `l` gives the best result ending at `i`.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * k)` | For each position, try up to `k` lengths |
| Space | `O(n)` | DP array |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def maxSumAfterPartitioning(self, arr: list[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            cur_max = 0
            for l in range(1, min(k, i) + 1):
                cur_max = max(cur_max, arr[i - l])
                dp[i] = max(dp[i], dp[i - l] + cur_max * l)

        return dp[n]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxSumAfterPartitioning([1,15,7,9,2,5,10], 3) == 84
    assert s.maxSumAfterPartitioning([1,4,1,5,7,3,6,1,9,9,3], 4) == 83
    assert s.maxSumAfterPartitioning([1], 1) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `k=3` example | `84` | Optimal partition with k=3 |
| Longer array | `83` | Greedy k=4 partitions |
| Single element | `1` | No partition needed |