Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1121. Partition Array for Maximum Sum

My accepted Python solution to LeetCode problem 1121, Partition Array for Maximum Sum, running in 249ms.

  • Difficulty: Medium
  • Python
  • Runtime 249ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 249ms, memory 17.4MB, accepted 2026-01-02.

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):
            max_val = 0
            # Try all partition sizes from 1 to k
            for j in range(1, min(k, i) + 1):
                max_val = max(max_val, arr[i - j])
                dp[i] = max(dp[i], dp[i - j] + max_val * j)
        
        return dp[n]

Source