254. Partition Array for Maximum Sum

🔗 LeetCode Problem: 1043. Partition Array for Maximum Sum
📊 Difficulty: Medium
🏷️ Topics: Array, Dynamic Programming, DP - MCM (Matrix Chain Multiplication)

Problem Statement

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.

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] <= 10^9 - 1 <= k <= arr.length

---

🧒 Starting From Absolute Zero - Understanding The Problem

What Does This Problem Ask?

Let me work through Example 1 VERY SLOWLY by hand:

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

Rules:
  1. Split array into groups (consecutive elements)
  2. Each group can have AT MOST k=3 elements
  3. Replace all elements in group with the MAX of that group
  4. Return the maximum possible sum

Let me try ONE specific way to understand:

Split as: [1, 15, 7] | [9, 2, 5] | [10]
         └─3 elements─┘ └─3 elements─┘ └1─┘

Step 1: Find max of each group
  [1, 15, 7] → max = 15
  [9, 2, 5] → max = 9
  [10] → max = 10

Step 2: Replace all with max
  [1, 15, 7] → [15, 15, 15]
  [9, 2, 5] → [9, 9, 9]
  [10] → [10]

Step 3: Calculate sum
  [15, 15, 15, 9, 9, 9, 10]
  = 15+15+15 + 9+9+9 + 10
  = 45 + 27 + 10
  = 82

Is this the best? Let me try another way...

Split as: [1, 15, 7] | [9] | [2, 5, 10]
         └─3 elements─┘ └1─┘ └─3 elements─┘

Step 1: Find max of each group
  [1, 15, 7] → max = 15
  [9] → max = 9
  [2, 5, 10] → max = 10

Step 2: Replace all with max
  [1, 15, 7] → [15, 15, 15]
  [9] → [9]
  [2, 5, 10] → [10, 10, 10]

Step 3: Calculate sum
  [15, 15, 15, 9, 10, 10, 10]
  = 45 + 9 + 30
  = 84

This is better! 84 > 82 ✓

So different splits give different sums!
Question: Which split gives MAXIMUM sum?

Understanding With Simplest Example

arr = [1, 15]
k = 2

How many ways can I split this?

WAY 1: [1] | [15]
  [1] | [15]
  sum = 1 + 15 = 16

WAY 2: [1, 15]
  max = 15
  [15, 15]
  sum = 15 + 15 = 30 ✓

Maximum = 30

Why is WAY 2 better?
  Because 1 becomes 15!
  We "upgraded" the small number! 🔑

---

🤔 Approach 1: Brute Force - Try All Possible Partitions

The Recursive Idea

To find best partition of array starting at position 'pos':

  Try taking 1 element as first group:
    - Calculate contribution: max(arr[pos]) × 1
    - Recursively solve rest of array
    - Total = contribution + solve(rest)

  Try taking 2 elements as first group:
    - Calculate contribution: max(arr[pos], arr[pos+1]) × 2
    - Recursively solve rest of array
    - Total = contribution + solve(rest)

  ...up to k elements

  Try taking k elements as first group:
    - Calculate contribution: max(first k) × k
    - Recursively solve rest of array
    - Total = contribution + solve(rest)

Return MAXIMUM of all options! 🔑

Complete Brute Force Implementation

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        return solve(arr, 0, k);
    }

    // pos: current position in array
    // k: max group size
    // Returns: maximum sum for arr[pos...end]
    private int solve(int[] arr, int pos, int k) {
        // Base case: reached end
        if (pos == arr.length) {
            return 0;
        }

        int maxSum = 0;
        int maxInGroup = 0;

        // Try taking 1, 2, ..., up to k elements as next group
        for (int size = 1; size <= k && pos + size <= arr.length; size++) {
            // Update max in current group
            maxInGroup = Math.max(maxInGroup, arr[pos + size - 1]);

            // Contribution of this group
            int contribution = maxInGroup * size;

            // Recursively solve rest
            int restSum = solve(arr, pos + size, k);

            // Total sum
            int totalSum = contribution + restSum;

            maxSum = Math.max(maxSum, totalSum);
        }

        return maxSum;
    }
}

Complete Trace - Understanding Every Step

arr = [1, 15, 7], k = 3

solve(pos=0, k=3)
│
├─ size=1: Take 1 element [1]
│  maxInGroup = 1
│  contribution = 1 × 1 = 1
│  solve(pos=1, k=3)
│  │
│  ├─ size=1: Take [15]
│  │  maxInGroup = 15
│  │  contribution = 15 × 1 = 15
│  │  solve(pos=2, k=3)
│  │  │
│  │  ├─ size=1: Take [7]
│  │  │  maxInGroup = 7
│  │  │  contribution = 7 × 1 = 7
│  │  │  solve(pos=3, k=3)
│  │  │  │
│  │  │  └─ pos == 3, return 0
│  │  │  
│  │  │  totalSum = 7 + 0 = 7
│  │  │  maxSum = 7
│  │  │
│  │  └─ Return 7
│  │  
│  │  totalSum = 15 + 7 = 22
│  │  maxSum = 22
│  │
│  ├─ size=2: Take [15, 7]
│  │  maxInGroup = max(15, 7) = 15
│  │  contribution = 15 × 2 = 30
│  │  solve(pos=3, k=3)
│  │  │
│  │  └─ pos == 3, return 0
│  │  
│  │  totalSum = 30 + 0 = 30
│  │  maxSum = max(22, 30) = 30 ✓
│  │
│  └─ Return 30
│  
│  totalSum = 1 + 30 = 31
│  maxSum = 31
│
├─ size=2: Take 2 elements [1, 15]
│  maxInGroup = max(1, 15) = 15
│  contribution = 15 × 2 = 30
│  solve(pos=2, k=3)
│  │
│  └─ size=1: Take [7]
│     maxInGroup = 7
│     contribution = 7 × 1 = 7
│     solve(pos=3, k=3)
│     │
│     └─ pos == 3, return 0
│     
│     totalSum = 7 + 0 = 7
│     Return 7
│  
│  totalSum = 30 + 7 = 37
│  maxSum = max(31, 37) = 37
│
└─ size=3: Take 3 elements [1, 15, 7]
   maxInGroup = max(1, 15, 7) = 15
   contribution = 15 × 3 = 45
   solve(pos=3, k=3)
   │
   └─ pos == 3, return 0

   totalSum = 45 + 0 = 45
   maxSum = max(37, 45) = 45 ✓

Return 45 ✓

Why Brute Force Works But Is Slow

TIME COMPLEXITY:

At each position, we try up to k different sizes
For each size, we recursively solve rest

Recurrence: T(n) = k × T(n-1) + k × T(n-2) + ... + k × T(n-k)

This is exponential! Roughly O(k^n)

For n=7, k=3: roughly 3^7 = 2187 recursive calls ✗

SPACE: O(n) recursion depth

Need optimization! 🔑

---

💡 Observation: Overlapping Subproblems

The Key Discovery

Look at the recursion tree for [1, 15, 7]:

solve(pos=0)
├─ size=1 → solve(pos=1)
│           ├─ size=1 → solve(pos=2)
│           └─ size=2 → solve(pos=3)
├─ size=2 → solve(pos=2)  ← REPEATED!
└─ size=3 → solve(pos=3)

Notice: solve(pos=2) is called MULTIPLE times!

For larger arrays, same positions solved repeatedly!

Example: [1, 15, 7, 9, 2, 5, 10]

solve(pos=3) might be called from:
  - solve(pos=0) taking size=3
  - solve(pos=1) taking size=2
  - solve(pos=2) taking size=1

We're recalculating same thing! ✗

This is OVERLAPPING SUBPROBLEMS! 🔑

---

🎯 Approach 2: Memoization (Top-Down DP)

The Optimization

Since we solve same subproblems repeatedly,
let's CACHE the results!

memo[pos] = maximum sum for arr[pos...end]

When we need solve(pos):
  - Check if memo[pos] exists
  - If yes: return cached value ✓
  - If no: compute, cache, then return

Complete Memoization Implementation

class Solution {
    private Integer[] memo;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        memo = new Integer[arr.length];
        return solve(arr, 0, k);
    }

    private int solve(int[] arr, int pos, int k) {
        // Base case
        if (pos == arr.length) {
            return 0;
        }

        // Check cache
        if (memo[pos] != null) {
            return memo[pos];
        }

        int maxSum = 0;
        int maxInGroup = 0;

        // Try different group sizes
        for (int size = 1; size <= k && pos + size <= arr.length; size++) {
            maxInGroup = Math.max(maxInGroup, arr[pos + size - 1]);

            int contribution = maxInGroup * size;
            int restSum = solve(arr, pos + size, k);

            maxSum = Math.max(maxSum, contribution + restSum);
        }

        // Cache result
        memo[pos] = maxSum;
        return maxSum;
    }
}

Why Memoization Helps

WITHOUT memoization:
  solve(pos=2) computed every time it's needed
  Exponential recursive calls!

WITH memoization:
  solve(pos=2) computed ONCE
  All future calls return cached value

Number of unique subproblems: n (one per position)
Work per subproblem: O(k)
Total: O(n × k) ✓

MUCH faster! 🚀

Complexity

TIME: O(n × k)
  n positions
  k options per position
  Each computed once

SPACE: O(n)
  Memo array + recursion stack

---

🔍 Approach 3: Discovering Bottom-Up DP From Brute Force

Let Me Look At The Brute Force Pattern Again

In brute force, I had:

solve(pos=0) for [1, 15, 7]
├─ size=1: take [1], then solve(pos=1) for [15, 7]
├─ size=2: take [1,15], then solve(pos=2) for [7]
└─ size=3: take [1,15,7], then solve(pos=3) for []

And solve(pos=1) for [15, 7]
├─ size=1: take [15], then solve(pos=2) for [7]
└─ size=2: take [15,7], then solve(pos=3) for []

Wait... let me write what each solve() returns:

solve(pos=3) = 0 (empty array)
solve(pos=2) = ? (for array [7])
solve(pos=1) = ? (for array [15, 7])
solve(pos=0) = ? (for array [1, 15, 7])

I'm solving from RIGHT to LEFT (end to beginning)!

Can I solve from LEFT to RIGHT instead? 🤔

Let Me Try Thinking Differently

Instead of:
  "Starting from position 0, what groups should I make?"

What if I think:
  "If I've already handled arr[0...i-1], how do I add arr[i]?"

Let me try this with [1, 15, 7]:

STEP 1: Handle just arr[0] = [1]
  I can only make one group: [1]
  Sum = 1

  Let me call this: best[0] = 1
  (best sum for arr[0...0])

STEP 2: Handle arr[0...1] = [1, 15]
  Wait, I already know best[0] = 1 (for just [1])

  Now I'm adding 15. How can I use it?

  Option A: Make 15 its own group
    Previous part: [1] with sum = best[0] = 1
    New group: [15] with sum = 15
    Total: 1 + 15 = 16

  Option B: Group 15 WITH the previous element
    Make group: [1, 15]
    max = 15, so sum = 15 × 2 = 30
    Total: 30

  Which is better? 30 > 16!

  So best[1] = 30

STEP 3: Handle arr[0...2] = [1, 15, 7]
  I already know best[1] = 30 (for [1, 15])

  Now I'm adding 7. How can I use it?

  Option A: Make 7 its own group
    Previous part: [1, 15] with sum = best[1] = 30
    New group: [7] with sum = 7
    Total: 30 + 7 = 37

  Option B: Group 7 with last 1 element (just 15)
    Previous part: [1] with sum = best[0] = 1
    New group: [15, 7], max=15, sum = 15 × 2 = 30
    Total: 1 + 30 = 31

  Option C: Group 7 with last 2 elements (15 and 1)
    Previous part: nothing (before = 0)
    New group: [1, 15, 7], max=15, sum = 15 × 3 = 45
    Total: 0 + 45 = 45

  Which is best? 45!

  So best[2] = 45

Aha! I'm building the answer LEFT to RIGHT! 🔑

The Pattern I Just Discovered

For each position i, I'm asking:
  "How should I group the LAST few elements ending at i?"

If I take last 1 element as a group:
  I need: best answer before it + contribution of [arr[i]]
  = best[i-1] + max(arr[i]) × 1

If I take last 2 elements as a group:
  I need: best answer before them + contribution of [arr[i-1], arr[i]]
  = best[i-2] + max(arr[i-1], arr[i]) × 2

If I take last 3 elements as a group:
  I need: best answer before them + contribution of [arr[i-2], arr[i-1], arr[i]]
  = best[i-3] + max(arr[i-2], arr[i-1], arr[i]) × 3

I try all options and take MAXIMUM! 🔑

Let Me Verify This Works

arr = [1, 15, 7, 9], k = 3

best[0]: Just [1]
  Only option: [1]
  best[0] = 1 ✓

best[1]: arr[0...1] = [1, 15]
  Last 1: best[0] + 15×1 = 1 + 15 = 16
  Last 2: 0 + max(1,15)×2 = 0 + 15×2 = 30
  best[1] = max(16, 30) = 30 ✓

best[2]: arr[0...2] = [1, 15, 7]
  Last 1: best[1] + 7×1 = 30 + 7 = 37
  Last 2: best[0] + max(15,7)×2 = 1 + 15×2 = 31
  Last 3: 0 + max(1,15,7)×3 = 0 + 15×3 = 45
  best[2] = max(37, 31, 45) = 45 ✓

best[3]: arr[0...3] = [1, 15, 7, 9]
  Last 1: best[2] + 9×1 = 45 + 9 = 54
  Last 2: best[1] + max(7,9)×2 = 30 + 9×2 = 30 + 18 = 48
  Last 3: best[0] + max(15,7,9)×3 = 1 + 15×3 = 1 + 45 = 46
  best[3] = max(54, 48, 46) = 54 ✓

This works! 🎉

Now Let Me Compare With Brute Force

BRUTE FORCE (Top-Down):
  solve(pos) = "Starting at pos, try sizes 1,2,3..."

  solve(0) depends on solve(1), solve(2), solve(3)
  solve(1) depends on solve(2), solve(3)
  solve(2) depends on solve(3)

  Direction: LEFT → RIGHT (but computed RIGHT → LEFT)

BOTTOM-UP:
  best[i] = "For arr[0...i], what if last group has size 1,2,3?"

  best[0] computed first
  best[1] uses best[0]
  best[2] uses best[1], best[0]
  best[3] uses best[2], best[1], best[0]

  Direction: LEFT → RIGHT (and computed LEFT → RIGHT)

They're solving the SAME problem, just in OPPOSITE directions! 🔑

Drawing The Dependency Picture

For arr = [1, 15, 7, 9]

BRUTE FORCE dependencies:

solve(0) ──┬──> solve(1) ──┬──> solve(2) ──┬──> solve(3)
           │                │                │
           ├──> solve(2) ───┤                │
           │                                 │
           └──> solve(3) ────────────────────┘

Computed in order: solve(3) → solve(2) → solve(1) → solve(0)

BOTTOM-UP dependencies:

best[0] <──┬─── best[1] <──┬─── best[2] <──┬─── best[3]
           │                │                │
           └─── best[2] <───┤                │
                                             │
           └─── best[3] <────────────────────┘

Computed in order: best[0] → best[1] → best[2] → best[3]

Same dependencies, just REVERSED! 🔑

The Complete DP Recurrence (Derived!)

I discovered:

best[i] = maximum sum for arr[0...i]

To compute best[i], I try making the last group different sizes:

For size = 1:
  Last group: [arr[i]]
  Before: arr[0...i-1] with sum = best[i-1]
  Contribution: max(arr[i]) × 1 = arr[i]
  Total: best[i-1] + arr[i]

For size = 2:
  Last group: [arr[i-1], arr[i]]
  Before: arr[0...i-2] with sum = best[i-2]
  Contribution: max(arr[i-1], arr[i]) × 2
  Total: best[i-2] + max(arr[i-1], arr[i]) × 2

For size = 3:
  Last group: [arr[i-2], arr[i-1], arr[i]]
  Before: arr[0...i-3] with sum = best[i-3]
  Contribution: max(arr[i-2], arr[i-1], arr[i]) × 3
  Total: best[i-3] + max(arr[i-2], arr[i-1], arr[i]) × 3

...up to size = k

Take MAXIMUM of all options! 🔑

Formula:
  best[i] = max over size in [1, min(k, i+1)]:
              best[i-size] + maxOfLast(size) × size

Walking Through The Table Build

Let me build the table for arr = [1, 15, 7, 9], k = 3

Table: best[0], best[1], best[2], best[3]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTE best[0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [1]
Position: i = 0

Try size = 1:
  Last group: [1]
  Before: nothing (i-1 = -1, so use 0)
  max = 1
  contribution = 1 × 1 = 1
  total = 0 + 1 = 1

best[0] = 1

Table: [1, ?, ?, ?]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTE best[1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [1, 15]
Position: i = 1

Try size = 1:
  Last group: [15]
  Before: best[0] = 1
  max = 15
  contribution = 15 × 1 = 15
  total = 1 + 15 = 16

Try size = 2:
  Last group: [1, 15]
  Before: nothing (i-2 = -1, so use 0)
  max = max(1, 15) = 15
  contribution = 15 × 2 = 30
  total = 0 + 30 = 30 ← BETTER!

best[1] = max(16, 30) = 30

Table: [1, 30, ?, ?]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTE best[2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [1, 15, 7]
Position: i = 2

Try size = 1:
  Last group: [7]
  Before: best[1] = 30
  max = 7
  contribution = 7 × 1 = 7
  total = 30 + 7 = 37

Try size = 2:
  Last group: [15, 7]
  Before: best[0] = 1
  max = max(15, 7) = 15
  contribution = 15 × 2 = 30
  total = 1 + 30 = 31

Try size = 3:
  Last group: [1, 15, 7]
  Before: nothing (i-3 = -1, so use 0)
  max = max(1, 15, 7) = 15
  contribution = 15 × 3 = 45
  total = 0 + 45 = 45 ← BEST!

best[2] = max(37, 31, 45) = 45

Table: [1, 30, 45, ?]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMPUTE best[3]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Array: [1, 15, 7, 9]
Position: i = 3

Try size = 1:
  Last group: [9]
  Before: best[2] = 45
  max = 9
  contribution = 9 × 1 = 9
  total = 45 + 9 = 54 ← BEST!

Try size = 2:
  Last group: [7, 9]
  Before: best[1] = 30
  max = max(7, 9) = 9
  contribution = 9 × 2 = 18
  total = 30 + 18 = 48

Try size = 3:
  Last group: [15, 7, 9]
  Before: best[0] = 1
  max = max(15, 7, 9) = 15
  contribution = 15 × 3 = 45
  total = 1 + 45 = 46

best[3] = max(54, 48, 46) = 54

Table: [1, 30, 45, 54]

ANSWER: best[3] = 54 ✓

The Key Insight I Discovered

BRUTE FORCE asks:
  "Starting at position pos, what should I do?"
  → Needs to know future (what comes after)

BOTTOM-UP asks:
  "I've solved up to position i-1, how do I extend to i?"
  → Uses past (what came before)

Both answer the same question, just from different directions!

It's like:
  Brute force: Walking from START to END
  Bottom-up: Walking from END to START

  Same path, opposite directions! 🔑

Why Bottom-Up Is Better

BRUTE FORCE:
  ✓ Natural thinking (top-down)
  ✗ Needs recursion stack (space)
  ✗ Function call overhead (slower)

BOTTOM-UP:
  ✓ No recursion (less space)
  ✓ Faster (no function calls)
  ✓ Easier to optimize further
  ✗ Less natural (need to reverse thinking)

For implementation: Bottom-up is cleaner! ✓

The Implementation (Now I Understand Why!)

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];

        // Build table left to right
        for (int i = 0; i < n; i++) {
            int maxInGroup = 0;

            // Try different sizes for last group
            for (int size = 1; size <= k && i - size + 1 >= 0; size++) {
                // Update max as we extend group backwards
                maxInGroup = Math.max(maxInGroup, arr[i - size + 1]);

                // Calculate sum for this option
                int before = (i - size >= 0) ? dp[i - size] : 0;
                int contribution = maxInGroup * size;

                dp[i] = Math.max(dp[i], before + contribution);
            }
        }

        return dp[n - 1];
    }
}

Now I understand EVERY line:

for (int i = 0; i < n; i++)
→ Build table left to right, position by position

for (int size = 1; size <= k && i - size + 1 >= 0; size++)
→ Try making last group size 1, 2, ..., up to k
→ Condition i - size + 1 >= 0 ensures we don't go before array start

maxInGroup = Math.max(maxInGroup, arr[i - size + 1])
→ As we extend group backwards, update the max
→ size=1: max of [arr[i]]
→ size=2: max of [arr[i-1], arr[i]]
→ size=3: max of [arr[i-2], arr[i-1], arr[i]]

int before = (i - size >= 0) ? dp[i - size] : 0
→ Get best answer before this group
→ If i-size < 0, we're at array start, so before = 0

dp[i] = Math.max(dp[i], before + contribution)
→ Update dp[i] with best option found so far

Complexity Analysis (Now Clear!)

TIME: O(n × k)
  Outer loop: n iterations (one per position)
  Inner loop: up to k iterations (trying sizes)
  Total: n × k operations

  For n=500, k=500: 250,000 operations ✓

SPACE: O(n)
  Just the dp array
  No recursion stack needed!

---

📊 Complete Comparison

┌─────────────────┬────────────┬──────────┬─────────────┐
│ Approach        │ Time       │ Space    │ Style       │
├─────────────────┼────────────┼──────────┼─────────────┤
│ 1. Brute Force  │ O(k^n)     │ O(n)     │ Recursive   │
│                 │ Exponential│ Stack    │ Too slow ✗  │
├─────────────────┼────────────┼──────────┼─────────────┤
│ 2. Memoization  │ O(n × k)   │ O(n)     │ Top-down    │
│    (Top-Down)   │ Linear     │ Cache    │ Natural ✓   │
├─────────────────┼────────────┼──────────┼─────────────┤
│ 3. Bottom-Up DP │ O(n × k)   │ O(n)     │ Iterative   │
│    (Tabulation) │ Linear     │ DP array │ Clean ✓     │
└─────────────────┴────────────┴──────────┴─────────────┘

---

🔑 Key Insights

The Learning Journey

STEP 1: Work by hand
  ✅ Understand what problem asks
  ✅ Try different partitions manually
  ✅ See that different splits give different sums

STEP 2: Brute force
  ✅ Try ALL possible partitions recursively
  ✅ For each position, try sizes 1, 2, ..., k
  ✅ Complete trace shows all paths
  ✅ O(k^n) - too slow!

STEP 3: Observe pattern
  ✅ Same subproblems solved repeatedly
  ✅ solve(pos=2) computed many times
  ✅ Overlapping subproblems!

STEP 4: Memoization
  ✅ Cache results
  ✅ Each subproblem computed once
  ✅ O(n × k) - much faster!

STEP 5: Derive bottom-up
  ✅ Reverse the thinking
  ✅ Build from small to large
  ✅ Same complexity, cleaner code!

The Pattern: Partition DP

Template for this pattern:

1. Try different sizes for last partition
2. For each size:
     - Calculate contribution of that partition
     - Add to optimal answer before it
3. Take maximum

---

💻 Complete Working Code

class Solution {
  public int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;
    int[] dp = new int[n];

    for (int i = 0; i < n; i++) {
      int maxInGroup = 0;

      for (int size = 1; size <= k && i - size + 1 >= 0; size++) {
        maxInGroup = Math.max(maxInGroup, arr[i - size + 1]);

        int before = (i - size >= 0) ? dp[i - size] : 0;
        int contribution = maxInGroup * size;

        dp[i] = Math.max(dp[i], before + contribution);
      }
    }

    return dp[n - 1];
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(sol.maxSumAfterPartitioning(new int[] {1,15,7,9,2,5,10}, 3)); // 84
    System.out.println(sol.maxSumAfterPartitioning(new int[] {1,4,1,5,7,3,6,1,9,9,3}, 4)); // 83
    System.out.println(sol.maxSumAfterPartitioning(new int[] {1}, 1)); // 1
  }
}

---

📝 Quick Revision

🎯 Core Algorithm

BRUTE FORCE:
  solve(pos) = try sizes 1..k, recursively solve rest
  O(k^n) - exponential

MEMOIZATION:
  Cache solve(pos)
  O(n × k)

BOTTOM-UP:
  dp[i] = max sum for arr[0...i]
  Try last group sizes 1..k
  dp[i] = max(dp[i-size] + max×size)
  O(n × k)

🔑 Quick Implementation

public class Solution {
  public int maxSumAfterPartitioning(int[] a, int k) {
    // return recursive(a, k, 0);

    // Integer[] memo = new Integer[a.length];
    // return topDown(a, k, 0, memo);

    return bottomUp(a, k);
  }

  private int bottomUp(int[] a, int k) {
    int n = a.length;
    int[] dp = new int[n];
    // dp[i]: result till a[0...i]
    // base case
    dp[0] = a[0];

    for (int i = 1; i < a.length; i++) {
      // Example consideration: [1, 15, 7, 9] and k = 3
      // step 1: I am at i = 1. I can take [15] or [1,15]
      // if i take 15, i need to add to result till earlier which is dp[0]
      // For example, i calculate dp[2] for [1,15,7]
      // if i am at i = 3 9, I can take 9 or (7,9) or (15,7,9)
      // if I take 9 alone, its 9 + dp[2] (res before this)
      // if I take (7,9), its (9*2) + dp[1]
      // if I take (15,7,9), its (15*3) + dp[0]
      dp[i] = a[i];
      int maxInGroup = 0;
      int res = 0;
      for (int size = 1; size <= k && i - size + 1 >= 0; size++) {
        maxInGroup = Math.max(maxInGroup, a[i - size + 1]);

        int groupSum = maxInGroup * size;

        int rest = (i - size >= 0) ? dp[i - size] : 0;

        int total = groupSum + rest;

        res = Math.max(res, total);
      }

      dp[i] = res;
    }

    return dp[n - 1];
  }

  private int topDown(int[] a, int k, int index, Integer[] memo) {
    if (index == a.length) {
      return 0;
    }

    if (memo[index] != null) {
      return memo[index];
    }

    int maxInGroup = 0;
    int res = 0;
    for (int size = 1; size <= k && index + size <= a.length; size++) {
      maxInGroup = Math.max(maxInGroup, a[index + size - 1]);

      int groupSum = maxInGroup * size;

      int rest = topDown(a, k, index + size, memo);

      int total = groupSum + rest;

      res = Math.max(res, total);
    }

    return memo[index] = res;
  }

  private int recursive(int[] a, int k, int index) {
    // step 7: base case
    if (index == a.length) {
      return 0;
    }

    // step 1: starting at index = 0
    // At index = 0, we have to take elements in groups of sizes from 1 to k.
    // index checking in below loop (index + size <= a.length) ?
    // consider index = 0 and size = 1 for array length 1 => 1 <= 1

    // simple run for [1, 15, 7, 9, 2, 5, 10] and k =3
    // if k = 3, we can take subarrays of sizes 1, 2, 3
    // we take subarray [1] and solve for rest (15,7,....10)
    // we take subarray [1,15] and solve for rest (7,....10)
    // we take subarrays [1,15,7] and solve for rest (9,....10)
    // in that taken subarray, check max and find result for that subarray.
    int maxInGroup = 0;
    int res = 0;
    for (int size = 1; size <= k && index + size <= a.length; size++) {
      // step 2: considering groups of sizes 1 to k, we are finding max
      // element till that k sized groups.
      maxInGroup = Math.max(maxInGroup, a[index + size - 1]);

      // step 3: find max group sum with this max element till now
      int groupSum = maxInGroup * size;

      // step 4: check for the rest of the array.
      int rest = recursive(a, k, index + size);

      // step 5: total at this moment
      int total = groupSum + rest;

      // step 6: update global res.
      res = Math.max(res, total);
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.maxSumAfterPartitioning(new int[] { 1, 15, 7, 9, 2, 5, 10 }, 3) == 84);
  }
}

⚡ Complexity

TIME: O(n × k)
SPACE: O(n)

---

🎉 Congratulations!

You've mastered: - ✅ Understanding by working examples - ✅ Brute force recursive solution - ✅ Identifying overlapping subproblems - ✅ Memoization optimization - ✅ Bottom-up DP derived from brute force - ✅ Complete baby-to-expert progression!

Partition DP pattern mastered! 🚀✨🎯