1
class Solution:
2
    def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
3
        def get_max(start, end):
4
            return max(nums[start : end + 1]) * (end - start + 1)
5

6
        def dfs(start):
7
            if (
8
                start == N
9
            ):  # base case, so in tabulation we go [N - 1]...[0], as [N] = 0
10
                return 0
11

12
            maxi = float(-inf)
13
            # you partition at every position up to start + k and repeat the same process for the next partition
14
            # e.g. 1 9 3, k = 2
15
            # 1|9|3 => with max in each partition: 1|9|3 = 13
16
            # 1|9 3 => with max in each partition: 1|9 9 = 19
17
            # 1 9|3 => with max in each partition: 9 9|3 = 21
18
            # get max_in_partition(start,end) + give_me_max_for_array(previous_partition_end + 1, N)
19
            # rec.relation = max(max_sum_in_partition[start, end] + dfs(end + 1)))
20
            for end in range(start, min(N, start + k)):
21
                maxi = max(maxi, get_max(start, end) + dfs(end + 1))
22
            return maxi
23

24
        N = len(nums)
25
        return dfs(0)