1043. Partition Array for Maximum Sum - Explanation

1. Recursion

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        def dfs(i):
            if i >= len(arr):
                return 0

            cur_max = 0
            res = 0
            for j in range(i, min(len(arr), i + k)):
                cur_max = max(cur_max, arr[j])
                window_size = j - i + 1
                res = max(res, dfs(j + 1) + cur_max * window_size)

            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$ for recursion stack.

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

2. Dynamic Programming (Top-Down)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        cache = { len(arr) : 0 }

        def dfs(i):
            if i in cache:
                return cache[i]

            cur_max = 0
            res = 0
            for j in range(i, min(len(arr), i + k)):
                cur_max = max(cur_max, arr[j])
                window_size = j - i + 1
                res = max(res, dfs(j + 1) + cur_max * window_size)

            cache[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

3. Dynamic Programming (Bottom-Up)

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

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

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .

4. Dynamic Programming (Space Optimized)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * k
        dp[0] = arr[0]

        for i in range(1, len(arr)):
            cur_max = 0
            max_at_i = 0
            for j in range(i, i - k, -1):
                if j < 0:
                    break
                cur_max = max(cur_max, arr[j])
                window_size = i - j + 1
                cur_sum = cur_max * window_size
                sub_sum = dp[(j - 1) % k] if j > 0 else 0
                max_at_i = max(max_at_i, cur_sum + sub_sum)

            dp[i % k] = max_at_i

        return dp[(len(arr) - 1) % k]

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(k)$

Where $k$ is the maximum length of the subarray and $n$ is the size of the array $arr$ .