Given an integer array arr, you should 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] <= 109
1 <= k <= arr.length

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def maxSumAfterPartitioning(self, arr, k):
        res = [0]
        
        for idx, val in enumerate(arr):
            max_val, cur_val = 0, 0
            
            for i in range(max(0, idx-k+1), idx+1)[::-1]:
                
                if arr[i] > max_val:
                    max_val = arr[i]
                    
                if res[i] + (idx-i+1)*max_val > cur_val:
                    cur_val = res[i] + (idx-i+1)*max_val
                    
            res.append(cur_val)
        return res[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
#         i = 0
#         temp = deque()
#         orig_k = K
#         while i < len(A):
#             temp.append(max(A[i:K]))
#             i = K
#             K *= 2
#         print(temp)
        
#         answer = deque()
#         while temp:
#             for _ in range(len(temp)):
#                 current_max = max(temp)
#                 #print(current_max)
#                 for _ in range(orig_k):
#                     answer.append(current_max)
#                     if len(answer) == len(A):
#                         break
#                     print(answer)
#                 temp.remove(current_max)
#         return sum(answer)

        ans=[0]
        
        for r, n in enumerate(A):
            maxVal, curVal = 0, 0
            
            for l in range(max(0, r-K+1), r+1)[::-1]:
                if A[l]>maxVal:
                    maxVal=A[l]
                
                if ans[l]+(r-l+1)*maxVal>curVal:
                    curVal=ans[l]+(r-l+1)*maxVal
           
            ans.append(curVal)
        
        return ans[-1]
                    


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [A[0]]
        
        
        for i in range(1, len(A)):
            max_partition_sum = A[i] + dp[-1]
            max_element = A[i]
            end = i - K
            
            
            if (end < -1):
                end = -1
                
                
            for j in range(i - 1, end, -1):
                if (A[j] > max_element):
                    max_element = A[j]
                    
                partition_sum = (i - j + 1) * max_element
                
                
                if (j > 0):
                    partition_sum += dp[j - 1]
                    
                    
                if (partition_sum > max_partition_sum):
                    max_partition_sum = partition_sum
                    
            dp.append(max_partition_sum)
            
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        return self.dp(arr, 0, k, {})
    
    
    def dp(self, arr, i, k, hashmap):
        if i>=len(arr):
            return 0
        
        if i in hashmap:
            return hashmap[i]
        
        largest = 0
        ans = 0
        for idx in range(k):
            if idx + i >=len(arr):
                break
            largest = max(largest, arr[i+idx])
            ans = max(ans, largest*(idx+1) + self.dp(arr, i+idx+1, k, hashmap))
        
        hashmap[i] = ans
        return ans
            


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        return self.recur(arr, len(arr)-1, k, {})

    def recur(self, arr, index, k, hashMap):
        if index < 0:
            return 0
        
        if index in hashMap:
            return hashMap[index]
        result = 0
        maxV = 0
        for i in range(k):
            if index - i < 0:
                continue
            maxV = max(maxV, arr[index-i])
            result = max(result, maxV * (i +1 ) + self.recur(arr, index-i-1, k, hashMap))
        
        hashMap[index] =  result
        return result

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        self.dp = {}
        
        def recur(index,arr,k):
            if index >= len(arr):
                return 0
            if index in self.dp:
                return self.dp[index]
            maxi = 0
            res = 0
            for i in range(k):
                if index+i < len(arr):
                    maxi = max(maxi, arr[index+i])
                    res = max(res, maxi * (i+1) + recur(index + i + 1, arr, k))
            self.dp[index] = res
            return res
        return recur(0, arr, k)

class Solution:
    def util(self,i,n,A,K,d) :
        if i >= n :
            return 0
        if i not in d :
            count=0
            ma=A[i]
            temp=-1
            while (i + count < n) and count<=K-1 :
                if A[i+count] > ma :
                    ma=A[i+count]
                nex=self.util(i+count+1,n,A,K,d)
                if (count+1)*ma+nex > temp :
                    temp=(count+1)*ma+nex
                count+=1
            d[i]=temp
        return d[i]
    
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n=len(A)
        d={}
        return self.util(0,n,A,K,d)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        visited={}
        
        def recurse(index):
            if index>=len(A):
                return 0
            if index in visited:
                return visited[index]
            mxx=0
            ans=0
            for i in range(K):
                if index+i<len(A):
                    mxx=max(mxx,A[i+index])
                    ans=max(ans,mxx*(i+1)+recurse(i+index+1))
            visited[index]=ans
            return ans
        return recurse(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = {}
        def recur(index,arr,k):
            if index >= len(arr):
                return 0
            if index in dp:
                return dp[index]
            maxi = 0
            res = 0
            for i in range(k):
                if index+i < len(arr):
                    maxi = max(maxi, arr[index+i])
                    res = max(res, maxi * (i+1) + recur(index + i + 1, arr, k))
            dp[index] = res
            return res
        return recur(0, arr, k)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0]*(n+1)
        for i in range(n):
            curMax = 0
            for k in range(1, min(K,i+1)+1 ):
                curMax = max(curMax, A[i-k+1])
                dp[i] = max(dp[i], dp[i-k]+curMax*k)
        
        print(dp)
        return dp[n-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = {}
        def recur(i,arr,k):
            if i >= len(arr):
                return 0
            if i in dp:
                return dp[i]
            maxi,res = 0,0
            for j in range(k):
                if i+j < len(arr):
                    maxi = max(maxi, arr[i+j])
                    res = max(res, maxi * (j+1) + recur(i + j + 1, arr, k))
            dp[i] = res
            return res
        return recur(0, arr, k)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp=[0]*len(arr)
        dp[0]=arr[0]
        max_value=arr[0]
        max_sum=arr[0]
        for i in range(1,k):
            max_value=max(max_value,arr[i])
            dp[i]=max_value*(i+1)
        for i in range(k,len(arr)):
            max_value=0
            for j in range(k):
                max_value=max(max_value,arr[i-j])
                dp[i]=max(dp[i],dp[i-j-1]+max_value*(j+1))
        return dp[-1]


from collections import deque

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = deque([0 for i in range(K)])
        for i in range(1, len(A)+1):
            maxA, maxP = float('-inf'), float('-inf')
            for j in range(1, min(K+1, i+1)):
                maxA = max(maxA, A[i-j])
                maxP = max(maxP, dp[-j] + j*maxA)
            dp.popleft()
            dp.append(maxP)
        return dp[-1]

from collections import deque

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = deque([0 for i in range(K)])
        for i in range(1, len(A)+1):
            maxA, maxP = float('-inf'), float('-inf')
            for j in range(1, min(K, i)+1):
                maxA = max(maxA, A[i-j])
                maxP = max(maxP, dp[-j] + j*maxA)
            dp.popleft()
            dp.append(maxP)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        inf = 0x3f3f3f3f
        dp = [[(-inf, -inf) for _ in range(k+1)] for _ in range(2)]
        last_max = 0
        dp[0][0] = (0, 0)
        for i in range(1, len(arr) + 1):
            for j in range(1, k + 1):
                if j == 1:
                    dp[i%2][j] = (last_max + arr[i-1], arr[i-1])
                    last_max = dp[i%2][j][0]
                elif i >= j:
                    last_s, last_n = dp[(i-1)%2][j-1]
                    n = max(last_n, arr[i-1])
                    s = last_s - last_n * (j-1) + n * j
                    dp[i%2][j] = (s, n)
                    last_max = max(last_max, s)
            #    print(i, j, dp[i][j])
        return last_max

class Solution:
    def maxSumAfterPartitioning(self, A, K):
            N = len(A)
            dp = [0] * (N + 1)
            for i in range(N):
                curMax = 0
                for k in range(1, min(K, i + 1) + 1):
                    curMax = max(curMax, A[i - k + 1])
                    dp[i] = max(dp[i], dp[i - k] + curMax * k)
                    
            return dp[N - 1]
    
    #Time Complexity- O(N*K)


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        if K == 1 or N == 1:
            return sum(A)
        
        dp = [0] * (N + 1)
        dp[0] = 0
        for i in range(N):
            mv = A[i]
            dp[i+1] = dp[i] + A[i]
            for j in range(1, min(i+1, K)):
                mv = max(mv, A[i-j])
                dp[i+1] = max(dp[i+1], dp[i-j] + (j+1)*mv)
                
        # print(dp)
        return dp[N]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:    
        size = len(A)
        if K == 1: return sum(A)
        dp = [0] * (size+1)
        for i in range(size):
            cur_max = A[i]
            block_size = 1
            while block_size <= K and i - block_size + 1 >= 0:
                cur_max = max(cur_max, A[i-block_size + 1])
                dp[i+1] = max(dp[i+1], dp[i-block_size + 1] + block_size * cur_max)
                block_size += 1
        
        return dp[size]



class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
       
        n=len(arr)
        dp=[[-1]*(n+1) for _ in range(n+1)]
        def maxsum(i=0):
            if i>=n:return 0 
            
            elif dp[i][n]!=-1:
                return dp[i][n]
            else:
                
                
                mx=0
                for j in range(i,min(i+k,n)): 
                    mx=max(arr[j],mx)
                    dp[i][j]=mx*(j-i+1)
                    dp[i][n]=max(dp[i][n],dp[i][j]+maxsum(j+1))
                return dp[i][n]
        return maxsum()
                    


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (n := len(arr))
        dp[0] = curr_max = arr[0]
        for i in range(1, k):
            curr_max = max(curr_max, arr[i])
            dp[i] = (i + 1) * curr_max
        for i in range(k, n):
            curr_max = arr[i]
            for j in range(k):
                curr_max = max(curr_max, arr[i-j])
                dp[i] = max(dp[i], dp[i-j-1] + (j + 1) * curr_max)
        return dp[-1]
        
        # @lru_cache(None)
        # def dp(idx):
        #     if idx < 0:
        #         return 0
        #     left = max(idx - k + 1, 0)
        #     curr_max = arr[idx]
        #     res = arr[idx]
        #     for i in range(idx, left - 1, -1):
        #         curr_max = max(curr_max, arr[i])
        #         res = max(res, dp(i-1) + (idx - i + 1) * curr_max)
        #     return res
        # return dp(len(arr) - 1)
        
        # A = arr
        # dp = [0] * (n := len(arr))
        # dp[0] = curr_max = arr[0]
        # for i in range(1, k):
        #     curr_max = max(curr_max, A[i])
        #     dp[i] = (i + 1) * curr_max
        # for i in range(k, n):
        #     curr_max = A[i]
        #     for j in range(k):
        #         curr_max = max(curr_max, A[i-j])
        #         dp[i] = max(dp[i], dp[i-j-1] + curr_max * (j + 1))
        # return dp[-1]


from collections import deque

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = deque([0 for i in range(K)])
        for i in range(1, len(A)+1):
            maxA, maxP = float('-inf'), float('-inf')
            for j in range(1, min(K+1, i+1)):
                maxA = max(maxA, A[i-j])
                maxP = max(maxP, dp[-j] + j*maxA)
            dp.popleft()
            dp.append(maxP)
        return dp.pop()

'''
what would be the state ? 
i: current position 
partition start 

just try allof them is probably the answer

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

try all possible partitions and keep track of the max and sum so far 


helper(start, i)

    for j in range(i, k - i + start + 1): # these are the possible ends 
        helper(start, j)
    
    
if i = 2 and start = 1 and k = 3
from i=2 to 5 - 1 = 4
instead it should be 1, 2, 3, so only one more so i + 1 = i + k - i 

if i = 2 and start = 1 and k = 4
it shld be 1, 2, 3, 4

i just want to know much left to get to k 
k = end - start 
k = j + i - start -> j = k - i + start

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        def helper(i, left, curr_max, sum_so_far):
            print(\"helper i =\", i, \", left =\", left, \", curr_max =\", curr_max)
            
            if i == len(arr):
                self.res = max(self.res, sum_so_far + (curr_max * (k - left)))
                return 0
            
            # continue current partition
            choice1 = float('-inf')
            if left > 0:
                choice1 = helper(i + 1, left - 1, max(curr_max, arr[i]), sum_so_far)
            
            # start a new partition
            choice2 = helper(i + 1, k, arr[i], sum_so_far + (curr_max * (k - left)))
            
            print(\"choice1 =\", choice1, \", choice2 =\", choice2)
            return max(choice1, choice2)
            
        self.res = float('-inf')
        helper(0, k, arr[0], 0)
        return self.res
'''

'''
dp[i]: max sum for arr ending at i 
'''
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], K: int) -> int:
        n = len(arr)
        dp = [0 for _ in range(n+1)]
        for i in range(n): # i is considered the end of the partition 
            currMax = 0
            for k in range(1, min(K, i + 1) + 1):
                currMax = max(currMax, arr[i - k + 1])
                dp[i] = max(dp[i], dp[i-k] + (currMax * k))
        return dp[n-1]

        
        
        
        




class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        if arr is None or len(arr) == 0:
            return 0
        
        dp = [0 for _ in range(len(arr))]
        
        for i in range(len(arr)):
            max_elem = arr[i]
            j = 1
            
            while j <= k and i - j + 1 >= 0:
                
                max_elem = max(max_elem, arr[i - j + 1])
                
                if i - j >= 0:
                    dp[i] = max(dp[i], max_elem * j + dp[i - j])
                    
                else:
                    dp[i] = max(dp[i], max_elem * j)
                
                j += 1
                    
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i, a in enumerate(A):
            r = a
            for j in range(1, K+1):
                r = max(r, A[i-j+1] if i-j+1>=0 else float('-inf'))
                # print(i, j, r, dp)
                if i-j+1 >= 0:
                    dp[i+1] = max(dp[i+1], dp[i-j+1] + r*j)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        cacheMax=[[0]*len(arr) for i in range(len(arr))]
        for i in range(len(arr)):
            cacheMax[i][i]=arr[i]
        for i in range(1,len(arr)):
            for j in range(i):
                cacheMax[j][i] = max(cacheMax[j][i-1],arr[i])
        
        
        
        
        dp=[0]*(len(arr)+1)
        dp[1]=arr[0]
        for i in range(1,len(arr)):
            for j  in range(max(0,i-k+1),i+1):
                dp[i+1]=max(dp[i+1],dp[j]+cacheMax[j][i]*(i-j+1))
                
            
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        self.dp = [-1 for i in range(n)]
        def helper(pos:int)->int:
            if pos >= n:
                return 0
            if self.dp[pos] != -1:
                return self.dp[pos]
            current_max = arr[pos]
            ret = arr[pos] + helper(pos+1)
            for i in range(1, k):
                pos2 = pos + i
                if pos2 >= n:
                    break
                current_max = max(current_max, arr[pos2])
                ret = max(ret, current_max * (i+1) + helper(pos2+1))
            self.dp[pos] = ret
            return ret
        return helper(0)


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        # maxSum[i] = max(A[i] + maxSum[i+1], max(A[i], A[i+1]) + maxSum[i+2], max(A[i], A[i+1], A[i+2], maxSum[i+3]))
        maxSum = [0] * n;
        for i in range(-1, -K-1, -1):
            maxSum[i] = max(A[i:])*(-i)
        for i in range(n-K-1, -1, -1):
            ms = 0
            for k in range(1, K+1):
                ms = max(ms, max(A[i:i+k]) * k + maxSum[i+k])
                # print(i,k,ms)
            maxSum[i] = ms
        # print(maxSum)
        return maxSum[0]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        @lru_cache(None)
        def helper(index, start, mx):
            if index == len(arr):
                return (index - start)* mx
            
            if index - start + 1 <= k:
                return max(helper(index + 1, start, max(arr[index], mx)), (index - start)*mx + helper(index + 1, index , arr[index]))
            
            return (index - start)*mx + helper(index + 1, index , arr[index])
        
        return helper(0, 0, arr[0])

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        inf = 0x3f3f3f3f
        dp = [[(-inf, -inf) for _ in range(k+1)] for _ in range(len(arr)+1)]
        last_max = 0
        dp[0][0] = (0, 0)
        for i in range(1, len(arr) + 1):
            for j in range(1, k + 1):
                if j == 1:
                    dp[i][j] = (last_max + arr[i-1], arr[i-1])
                    last_max = dp[i][j][0]
                elif i >= j:
                    last_s, last_n = dp[i-1][j-1]
                    n = max(last_n, arr[i-1])
                    s = last_s - last_n * (j-1) + n * j
                    dp[i][j] = (s, n)
                    last_max = max(last_max, s)
            #    print(i, j, dp[i][j])
        return last_max

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0] * len(A)
        for i in range(K):
            dp[i] = max(A[:(i + 1)]) * (i + 1)
        for i in range(K, len(A)):
            dp[i] = max([dp[i - j] + max(A[(i - j + 1):(i + 1)]) * j for j in range(1, K + 1)])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        '''
        For each element, it can either go to the previous group, or start a new group
        dp[i][j] = largest sum before i when last group's size is j, last group's largest value
        '''
        dp = [[(0, 0)] * k for _ in range(len(arr)+1)]
        for i in range(1, len(arr)+1):
            for j in range(min(i, k)):
                if j == 0:
                    dp[i][j] = max((dp[i-1][m][0] + arr[i-1], arr[i-1]) for m in range(min(i, k)))
                else:
                    new_max = max(dp[i-1][j-1][1], arr[i-1])
                    dp[i][j] = dp[i-1][j-1][0] - j * dp[i-1][j-1][1] + new_max * (j + 1), new_max
        #print(dp)
        return max(dp[-1])[0]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0]*n
        for i in range(n-1, -1, -1):
            curr_max = arr[i]
            for j in range(0, k):
                index = min(n-1, i+j)
                curr_max = max(curr_max, arr[index])
                if i+j+1 >= n:
                    dp[i] = (n-i)*curr_max
                else:
                    dp[i] = max(dp[i], dp[i+j+1] + (j+1)*curr_max)
        return dp[0]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        if not arr:
            return 0
        
        
        local_max = {(idx, idx+1) :arr[idx] for idx in range(len(arr))}
        for l in range(2, k+1):
            for start in range(len(arr)-l+1):
                local_max[(start, start+l)] = max(local_max[(start, start+l-1)], local_max [(start+1, start+l)])
        
                
        f = [0]
        for end in range(1, len(arr)+1):
            _local = 0
            for start in range(max(0, end-k), end):
                _local = max(f[start]+local_max[(start, end)]*(end-start), _local)
            f.append(_local)
        return f[-1]
    
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        memo=[0]*n
        for i in range(n):
            if i<k:
                memo[i]=(i+1)*max(arr[:i+1])
            else:
                memo[i]=max(memo[i-j-1]+(j+1)*max(arr[i-j:i+1]) for j in range(k))
        return memo[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        # 动态规划
        length = len(arr)
        dp = [0]*(length+1)
        maxval = [[0]*length for _ in range(length)]
        for i in range(length):
            for j in range(i, length):
                if i == j:
                    maxval[i][j] = arr[i]
                else:
                    maxval[i][j] = max(maxval[i][j-1], arr[j])
        # print(maxval)
        for i in range(1, length+1):
            temp = 0
            # print(\"------{}------\".format(i))
            for t in range(1, k+1):
                temp = max(temp, dp[i-t]+maxval[i-t][i-1]*t)
                # print(temp)
            dp[i] = temp
        # print(dp)
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        dp = [0] * len(A)
        
        for i in range(K):
            dp[i] = (i+1) * max(A[:i+1])
        
        for i in range(K,len(A)):
            maximum = 0
            for j in range(1,K+1):
                if i-j<0:
                    break
                temp = dp[i-j] + max(A[i-j+1:i+1]) * j
                if temp>maximum:
                    maximum = temp
            dp[i] = maximum
            
        print(dp)
            
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        def dfs(i, j, max_num=0):
            if i == -1:
                return max_num * j

            if opt[i][j] == -1:
                a, b = 0, 0
                if j < K:
                    a = dfs(i - 1, j + 1, max(max_num, A[i]))
                b = j * max_num + dfs(i - 1, 1, A[i])
                opt[i][j] = max(a, b)
            return opt[i][j]

        n = len(A)
        opt = [[-1] * (K + 1) for _ in range(n)]
        return dfs(n - 1, 0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        l = len(arr)
        results = [0] * l
        for idx, num in enumerate(arr):
            if idx < k:
                results[idx] = max(arr[:idx+1]) * (idx + 1)
            else:
                res = 0
                for i in range(1, k+1):
                    start = idx -i
                   
                    tmp = results[start] + max(arr[start+1:idx+1]) * i
                
                    res = max(res, tmp)
                results[idx] = res

        return results[-1]


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

        for i in range(len(arr)):

            if i<=k-1:

                max_sums[i] = (i+1)*max(arr[:i+1])

            else:
             
                res = 0

                for j in range(1,k+1):

                    first = max_sums[i-j]
                    second = j*max(arr[i-j+1:i+1])

                    #print(i, j)
                    #print(arr[:i-j+1], arr[i-j+1:i+1])
                    #print(\"first, second \", first, second)
                    
                    res = max(res, first+second)        
                    
                max_sums[i] = res

            #print(max_sums)

        #print(max_sums)

        return max_sums[-1]



class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        maxx = arr[0]
        dp = []
        for i,_ in enumerate(arr[:k]):
            maxx=max(arr[i], maxx)
            dp.append(maxx*(i+1))
            
        for i, _ in enumerate(arr[k::]):
            i+=k
            max_sum = 0
            for j in range(k):
                max_sum = max(
                    max_sum,dp[i-j-1] + (max(arr[i-j:i+1])*(j+1))
                )
                
            dp.append(max_sum)
            
        return dp[-1]
                    
            
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        A=arr
        K=k
        n=len(A)
        dp=[0]*n
        for i in range(K):
            dp[i]=max(A[:i+1])*(i+1)
        for i in range(K,n):
            for j in range(1,K+1):
                dp[i]=max(dp[i],dp[i-j]+max(A[i-j+1:i+1])*j)
        return dp[-1]
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        size = len(arr)
        dp = [0]*size
        for i in range(k):
            dp[i] = max(arr[:i+1])*(i+1)
        
        for i in range(k,size):
            for j in range(1,k+1):
                dp[i] = max(dp[i],dp[i-j]+max(arr[i-j+1:i+1])*j)

        return dp[-1]

class Solution:
    def printm(self,arr):
        [print(arr[i]) for i in range(len(arr))]
    def maxSumAfterPartitioning(self, A,K):
        size = len(A)
        dp = [0]*size
        for i in range(K):
            dp[i] = max(A[:i+1])*(i+1)
        # printm(dp)

        for i in range(K,size):
            for j in range(1,K+1):
                dp[i] = max(dp[i],dp[i-j]+max(A[i-j+1:i+1])*j)
        # self.printm(dp)
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        L = len(arr)
        dp = [0] * L
        for i in range(k):
            dp[i] = max(arr[:i+1])*(i+1)
        for i in range(k,L):
            dp[i] = dp[i-k] + max(arr[i-k+1:i+1])*k
            for j in range(1,k):
                dp[i] = max(dp[i],dp[i-j] + max(arr[i-j+1:i+1])*j)
        return dp[-1]

# dynamic programming
# time complexity: O(A*K*K)
# dp[i] = max sum of A[:i] after partitioning
class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [float('-inf')] * (N+1)
        for i in range(1,N+1):
            if i <= K:
                dp[i] = max(A[:i]) * i
            else:
                for j in range(1,K+1):
                    dp[i] = max(dp[i], dp[i-j]+max(A[i-j:i])*j)
        return dp[-1]

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

        for i in range(k, len(arr)):
            for j in range(1,k+1):
                dp[i] = max(dp[i], dp[i-j] + j * max(arr[i-j+1:i+1]))
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        M = [0 for i in range(len(arr))]
        
        M[0] = arr[0]
        
        for i in range(1, len(arr)):
            
            if i < k:
                M[i] = max(arr[:i+1]) * (i+1)
            else:
                for j in range(1, min(k+1, i+1)):
                    M[i] = max(M[i], M[i-j] + max(arr[i-j+1:i+1]) * j)
            
        return M[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        rec = {}
        def helper(idx):
            if idx in rec:
                return rec[idx]            
            if len(arr)-idx <= k:
                temp = max(arr[idx:])*(len(arr)-idx)
                rec[idx] = temp
                return temp
            pre_max = float('-inf')
            temp = float('-inf')
            for j in range(idx, min(idx+k, len(arr))):
                pre_max = max(pre_max, arr[j])
                temp = max(temp, pre_max*(j-idx+1)+helper(j+1))
            rec[idx] = temp
            return temp
        
        return helper(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0]*len(arr)
        for i in range(k):
            dp[i] = max(arr[:i+1])*(i+1)
        #print(dp)
        for i in range(k,len(arr)):
            for j in range(1,k+1):
                dp[i] = max(dp[i],dp[i-j]+max(arr[i-j+1:i+1])*j)
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        def maxSum(i, mem):
            if i in mem: return mem[i]
            
            if len(A) - i <= K:
                mem[i] = max(A[i:]) * (len(A) - i)
                return mem[i]
            
            ans = -float('inf')
            for j in range(i+1, i+1+K):
                if j > len(A): break
                ans = max(ans, max(A[i:j]) * (j-i) + maxSum(j, mem))
            mem[i] = ans
            return mem[i]
        
        mem = {}
        return maxSum(0, mem)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        largest_sums = []
        for i in range(len(A)):
            if i < K:
                largest_sums.append(max(A[:i+1]) * (i + 1))
                continue
            
            max_sum = 0
            for j in range(K):
                if i - (j+1) < 0:
                    continue
                # print(j, i-j-1, largest_sums[i - j-1], max(A[i-j:i+1]))
                cur_sum = largest_sums[i - j-1] + max(A[i-j:i+1]) * (j + 1)
                if cur_sum > max_sum:
                    max_sum = cur_sum
            
            # print(i, max_sum)
            largest_sums.append(max_sum)
        
        return largest_sums[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        def dfs(i, j, max_num=0):
            if i == -1:
                return max_num * j

            if opt[i][j] == -1:
                ans = 0
                if j < K:
                    ans = max(ans, dfs(i - 1, j + 1, max(max_num, A[i])))
                ans = max(ans, j * max_num + dfs(i - 1, 1, A[i]))
                opt[i][j] = ans
            return opt[i][j]

        n = len(A)
        opt = [[-1] * (K + 1) for _ in range(n)]
        return dfs(n - 1, 0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0 for i in range(len(arr))]
        for i in range(k):
            dp[i] = (i+1)*max(arr[:i+1])
        for i in range(k,len(arr)):
            for j in range(k):
                dp[i] = max(dp[i], dp[i-j-1]+(j+1)*max(arr[i-j:i+1]))
        return dp[len(arr)-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * n
        
        for i in range(K):
            dp[i] = max(A[:i+1]) * (i + 1)
        
        for i in range(K, n):
            for d in range(1, K + 1):
                dp[i] = max(dp[i], dp[i - d] + max(A[i - d + 1: i + 1]) * d)
                
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        mm = [[a for a in arr]]
        for i in range(len(arr) - 1):
            mm.append([0] * len(arr))
        for i in range(1, k):
            for j in range(i, len(arr)):
                mm[i][j] = max(mm[i - 1][j - 1], arr[j])
        dp = [0] * (len(arr) + 1)
        for i in range(1, len(arr) + 1):
            for j in range(max(k, i)):
                dp[i] = max(dp[i], dp[i - j - 1] + mm[j][i - 1] * (j + 1))
        print(dp)
        return dp[-1]
                
        


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        aLen = len(A)
        dp = {}
        def helper(i0):
            if i0 in dp:
                return dp[i0]
            if aLen - i0 <= K:
                dp[i0] = max(A[i0:])*(aLen-i0)
                return dp[i0]
            subAns = 0
            thisMax = A[i0]
            for ki in range(1, K+1):
                thisMax = max(thisMax, A[i0+ki-1])
                subAns = max(subAns, thisMax*ki + helper(i0 +ki))
            dp[i0] = subAns
            return subAns
        return helper(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        maxes = [[None for _ in range(n)] for _ in range(n)]
        for i in range(n):
            maxes[i][i] = arr[i]
        for i in range(n):
            for j in range(i+1, n):
                maxes[i][j] = max(arr[j], maxes[i][j-1])
                
        dp = [None for _ in range(n+1)]
        dp[n] = 0
        for i in range(n-1, -1, -1):
            m = float('-inf')
            for j in range(min(n-i,k)):
                m = max(m, (j+1)*maxes[i][min(n-1, i+j)] + dp[min(n, i+j+1)])
            dp[i] = m
        return dp[0]
        
                


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        
        def helper(index, start, mx):
            key = (index, start, mx)
            if key in d:
                return d[key]
            if index == len(arr):
                return (index - start)* mx
            
            if index - start + 1 <= k:
                d[key] = max(helper(index + 1, start, max(arr[index], mx)), (index - start)*mx + helper(index + 1, index , arr[index]))
                return d[key]
            d[key] = (index - start)*mx + helper(index + 1, index , arr[index])
            return d[key]
        d = dict()
        return helper(0, 0, arr[0])

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        @lru_cache(None)
        def checkSum(i, j, k):
            if j - i <= k:
                return max(A[i:j]) * (j - i)
            else:
                best = 0
                for nk in range(1, K + 1):
                    best = max(best, checkSum(i, i + nk, K) + checkSum(i+nk, j, K))
            return best
        return checkSum(0, len(A), K)


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        arr = [[(0,0)]*(K+1) for _ in range(N)]
        prev=0
        for i in range(N):
            arr[i][1] = (A[i]+prev,A[i])
            prev+=A[i]
            for j in range(2,min(i+2,K+1)):
                mx = max(arr[i-1][j-1][1],A[i])
                s = arr[i-1][j-1][0] - arr[i-1][j-1][1]*(j-1) + mx*j
                arr[i][j] = (s,mx)
                prev = max(prev,s)
            # print(prev,arr[i][1:])
        return max(arr[-1][k][0] for k in range(1,K+1))
                


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        if not A:
            return 0
        N = len(A)
        if K == N:
            return N*max(A)
        dp = [0 for i in range(N)]
        for i in range(K):
            dp[i] = max(A[:i+1])*(i+1)
        for i in range(K, N):
            a = max(A[i-K+1:i+1])
            # print(a, dp[i-K], dp[i-1])
            # dp[i] = max(dp[i-K]+K*a, dp[i-1]+A[i])
            dp[i] = max([dp[i-j]+j*max(A[i-j+1:i+1]) for j in range(1, K+1)])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        @lru_cache(None)
        def help(A,K):
            n = len(A)
            if K==1:
                return sum(A)
            if K>=n:
                return n*max(A)
            cMax = [A[0]]
            for i in range(1,K):
                cMax.append(max(cMax[-1],A[i]))
            return max((i+1)*cMax[i] + help(A[i+1:],K) for i in range(K))
        return help(tuple(A),K)
            


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
      #dpdp
      grid = [0]*len(arr)
      for i in range(len(arr)-1, -1, -1):
        if len(arr) - i <= k:
          grid[i] = max(arr[i:len(arr)])*(len(arr)-i)
        else:
          maxi = 0
          current_max = 0
          for t in range(k):
            current_max = max(current_max, arr[i+t])
            maxi = max(maxi, current_max*(t+1) + grid[i+t+1])
          grid[i] = maxi
      return grid[0]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        if not arr:
            return 0
        
        if k==1:
            return sum(arr)
        
        self.memo={}
        
        def makepart(arr,n):
            
            if n in self.memo:
                return self.memo[n]
            
            if not arr:
                return 0
            
            l=min(k,len(arr))
            maxele=0
            total=0
            
            for i in range(l):
                
                maxele=max(maxele,arr[i])
                
                temp=(maxele*(i+1))+makepart(arr[i+1:],n+i+1)
                
                total=max(total,temp)
                
            self.memo[n]=total
            
            return total
        
        return makepart(arr,0)
                
            


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], k: int) -> int:
        def dfs(i, j, max_num=0):
            if i == -1:
                return max_num * j

            if (i, j, max_num) not in opt:
                ans = 0
                if j < k:
                    ans = max(ans, dfs(i - 1, j + 1, max(max_num, A[i])))
                ans = max(ans, j * max_num + dfs(i - 1, 1, A[i]))
                opt[(i, j, max_num)] = ans
            return opt[(i, j, max_num)]
        
        n = len(A)
        opt = dict()
        return dfs(n - 1, 0)


class Solution:
    def maxSumAfterPartitioning(self, arr, k: int) -> int:
        n = len(arr)
        mask = [[0] * n for i in range(n)]
        for i in range(n):
            for j in range(i, n):
                mask[i][j] = max(arr[j], mask[i][j - 1] if j > i else 0)

        for i in range(n):
            for j in range(i, n):
                mask[i][j] = (j + 1 - i) * mask[i][j]
        dp = [0]*n
        for i in range(n):
            for h in range(1,k+1):
                dp[i]= max((dp[i-h] if i-h>=0 else 0)+(mask[i-h+1][i] if i-h+1<n else 0), dp[i])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr, k: int) -> int:
        n = len(arr)
        mask = [[0] * n for i in range(n)]
        for i in range(n):
            for j in range(i, n):
                mask[i][j] = max(arr[j], mask[i][j - 1] if j > i else 0)

        for i in range(n):
            for j in range(i, n):
                mask[i][j] = (j + 1 - i) * mask[i][j]
                
        dp = [0]*n
        for i in range(n):
            for h in range(1,k+1):
                dp[i]= max((dp[i-h] if i-h>=0 else 0)+(mask[i-h+1][i] if i-h+1<n else 0), dp[i])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        self.answer = {}
        def max_starting_i (index_A):
            array = A[index_A:]
            if index_A in self.answer:
                return self.answer[index_A]
            #print (array)
            if len(array) == 0:
                self.answer[index_A] = 0
                return 0
            if len(array) <= K:
                self.answer[index_A] =  max(array) * len(array) 
                return self.answer[index_A] 
            max_start_here = 0
            for i in range(0,K):
                #print (i)
                max_split_here = (i+1)*max(array[:i+1]) + max_starting_i(index_A+i+1)
                max_start_here = max(max_start_here, max_split_here)
            self.answer[index_A]  = max_start_here
            return max_start_here
        
        return max_starting_i(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
      #dpdp
      grid = [0]*len(arr)
      for i in range(len(arr)-1, -1, -1):
        if len(arr) - i <= k:
          grid[i] = max(arr[i:len(arr)])*(len(arr)-i)
        else:
          maxi = 0
          for t in range(k):
            maxi = max(maxi, max(arr[i:i+t+1])*(t+1) + grid[i+t+1])
          grid[i] = maxi
      return grid[0]


class Solution:
    def maxSumAfterPartitioning(self, l: List[int], k: int) -> int:
        def _max_sum(l, start, k, memo):
            if (len(l)-start) <= k:
                return (len(l)-start)*max(l[start:])

            if start in memo:
                return memo[start]

            max_sum = l[start]
            for i in range(1, k+1):
                curr_sum = max(l[start:start+i])*i + _max_sum(l, start+i, k, memo)
                max_sum = max(max_sum, curr_sum)

            memo[start] = max_sum
            return max_sum


        if not l:
            return 0

        return _max_sum(l, 0, k, dict())

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
#         fMax = [A[0]]
#         for num in A[1:]:
#             fMax.append(max(fMax[-1], num))
        aLen = len(A)
#         bMax = [num for num in A]
#         for i in range(aLen-2, -1, -1):
#             bMax[i] = max(bMax[i], bMax[i+1])
        
#         ans = 0
#         for i in range(aLen-1):
#             ans = max(ans, (i+1)*fMax[i] + (aLen-i-1)*bMax[i+1])
#         return ans
        dp = {}
        def helper(i0):
            if i0 in dp:
                return dp[i0]
            if aLen - i0 <= K:
                dp[i0] = max(A[i0:])*(aLen-i0)
                return dp[i0]
            subAns = 0
            thisMax = A[i0]
            for ki in range(1, K+1):
                thisMax = max(thisMax, A[i0+ki-1])
                subAns = max(subAns, thisMax*ki + helper(i0 +ki))
            dp[i0] = subAns
            return subAns
        return helper(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        self.dp = [-1] * (len(arr)+k)
        return self.solve(arr, 0, k)
    
    def solve(self, arr, start, k):
        if start >= len(arr):
            return 0
        
        if start + k >= len(arr):
            end = min(len(arr), start+k)            
            return max(arr[start:end]) * (end-start)
        
        if self.dp[start] != -1:
            return self.dp[start]
        
        result = float('-inf')
        for p in range(1, k+1):
            temp = max(arr[start:start+p]) * p + self.solve(arr, start+p, k)
            result = max(temp, result)
        
        self.dp[start] = result
        return result

class Solution:
    def partition(self, arr, k, index, memo):
        if len(arr) == 0:
            return 0
        
        if index in memo:
            return memo[index]
        
        maxNum = arr[0]
        maxSum = maxNum
        for i in range(1, min(k+1, len(arr)+1)):
            maxNum = max(maxNum, arr[i-1])
            subarr = arr[:i]
            sumArr = self.partition(arr[i:], k, index + i, memo)
            # i is the size of the array you're examining
            sumArr += maxNum * (i)
            maxSum = max(sumArr, maxSum)
        
        memo[index] = maxSum
        return maxSum
            
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        memo = {}
        num = self.partition(arr, k, 0, memo)
        print(memo)
        return num

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        self.cache = {}
        
        def helper(arr, k, start):
            if start in self.cache:
                return self.cache[start]

            _arr = arr[start:]
            if len(_arr) == 0:
                return 0
            if len(_arr) <= k:
                return max(_arr) * len(_arr)

            ans = -1
            for i in range(1, k + 1):
                ans = max(ans, i * max(_arr[:i]) + helper(arr, k, start + i))

            self.cache[start] = ans
            return ans
    
        return helper(arr, k, 0)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i in range(1,n+1):
            # m = float('-inf')
            for j in range(1,K+1):
                if i - j >= 0:
                    m = max(A[i-j:i])
                    dp[i] = max(dp[i],dp[i-j]+m*j)
        return dp[-1]

import typing

class Solution:
    def maxSumAfterPartitioning(self, arr: typing.List[int], k: int) -> int:
        storage = {}
        def getSumRec(arr:list,i:int,k:int)->int:
            if i in storage:
                return storage[i]

            if not i<len(arr):
                return 0

            if len(arr) - i < k:
                return max(arr[i:])*len(arr[i:])

            listOfSums = []
            for offset in range(k):
                listOfSums.append( max(arr[i:i+offset+1] )*(offset+1) + getSumRec(arr,i+offset+1,k))

            storage[i] = max(listOfSums)
            return storage[i]

        return getSumRec(arr,0,k)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
         
        best_a = [0] * len(A)
        best_a[0] = A[0]
       
        for i in range(1, len(A)):
            max_v = 0
            for j in range(i, max(-1, i-K), -1):
                sa = A[j:i+1]
                v = best_a[j-1] + max(sa) * len(sa)
                if v > max_v:
                    max_v = v
                #print(best_a,max_v,i,j,sa)
            best_a[i] = max_v
        
        return best_a[-1]
        
        
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr)+1)
        for i in range(0, len(arr)):
            m = 0
            for j in range(i, i-k, -1):
                if j < 0:
                    break
                t = max(arr[j:i+1]) * (i - j + 1) + dp[j] 
                if t > m:
                    m = t
            dp[i+1] = m
            
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        best_a = [0] * len(A)
        best_a[0] = A[0]
        
        for i in range(1,len(A)):
            maxv = 0
            for j in range(i,max(-1,i - K),-1):
                sa = A[j:i + 1]
                v = best_a[j - 1] + max(sa) * len(sa)
                
                if v > maxv:
                    maxv = v
            best_a[i] = maxv
        return best_a[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        dp_sum=[0]*n
        
        dp_sum[0]=arr[0]
        max_so_far=arr[0]
        
        for i in range(1,k):
            max_so_far = max(max_so_far, arr[i])
            dp_sum[i] = (i+1)*max_so_far
        
        for i in range(k,n):
            partition_max = 0
            for back in range(k):
                partition_max = max(partition_max, arr[i-back])
                
                dp_sum[i] = max(dp_sum[i], dp_sum[i-back-1] + (back+1)*partition_max)
        
        return dp_sum[-1]


class Solution:
    
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        opt = [arr[0]]
        for i in range(1, len(arr)):

            opt.append(0)  # At index i
            
            subseqLenMax = min(k, i+1)  # To avoid counting past index 0
            
            # For the length of each possible subsequence which includes (and ends at) index i:
            for subseqLen in range(1, subseqLenMax+1):
                
                # Find the max possible sum of the subsequence
                subseqSum = subseqLen * max(arr[i-subseqLen+1 : i+1])
                
                # Add to the optimal solution from before
                if subseqLen < i+1:
                    prevOpt = opt[i-subseqLen]
                else:  # Entire arr
                    prevOpt = 0
                optTemp = prevOpt + subseqSum
                
                # print('for opt', i, ' sublen =', subseqLen, '   subseqSum = ',subseqSum, ' optTemp = ', optTemp)
                
                # Compare to the other possible subsequence sums
                if optTemp > opt[i]:
                    opt[i] = optTemp

            # print(opt)
            
        return opt[len(opt)-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        if K == 1:
            return sum(A)
        
        # dp[i]: ans considering A[0:i]
        dp = [0] * (len(A)+1)

        for i in range(1, len(A)+1):
            cand = []
            for j in range(1, K+1):
                # consider to A[i-j:i]
                if j > i:
                    break
                temp = dp[i-j] + max(A[i-j:i]) * j
                cand.append(temp)
            
            dp[i] = max(cand)
        
        print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            for w in range(1, K + 1):
                if i - w < 0: break
                dp[i] = max(dp[i], dp[i - w] + max(A[i - w:i]) * w)
            
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0 for i in range(len(A)+1)]
        
        dp[0] = 0
        dp[1] = A[0]
        for i in range(1, len(A)):
            result = 0
            for j in range(max(0, i-K+1), i+1):
                result = max(result, dp[j] + max(A[j:i+1])*(i-j+1))
            dp[i+1] = result
                                
        return dp[-1]
            


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):
            for j in range(1, min(k+1,i+1)):
                dp[i]= max(dp[i], dp[i-j]+ max(arr[i-j:i])*j)
        
        
        return dp[n]
        
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0]* (len(arr)+1)
        dp[1] = arr[0]
        for i in range(2, len(dp)):
            for j in range(1, k+1):
                if i-j < 0:
                    continue
                #print(i, j, i-j, i)
                dp[i] = max(dp[i], dp[i-j] + j * max(arr[i-j:i]))
        
        print(dp)
        return dp[len(arr)]
                
            
            
            


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

        if not arr:
            return 0
        
        if n == 1:
            return arr[0]
        
        if n < k:
            return sum(arr)
        
        dp = [0] * (n)
        
        for i in range(n):
            for j in range(i, max(-1, i-k), -1): 
                dp[i] = max(dp[i], max(arr[j:i+1]) * (i-j+1) + (dp[j-1] if j-1 >= 0 else 0))
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        N = len(arr)
        T = [0] * (N+1)
        for i in range(1, N+1):
            for j in range(1, k+1):
                if j > i: break
                #if i == 2: print(max(arr[(i-j): i]), arr[(i-j): i], j)
                T[i] = max(T[i], T[i-j] + max(arr[(i-j): i]) * j)
        #print(T)
        return T[N]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        
        M = [0 for i in range(len(arr))]
        
        M[0] = arr[0]
        
        #if len(arr) > 1:
        #    M[1] = max(arr[0],arr[1]) * 2
            
        #if len(arr) > 2:
        #    M[2] = max(arr[0],arr[1],arr[2]) * 3
            
        for i in range(1, len(arr)):
            
            if i < k:
                M[i] = max(arr[:i+1]) * (i+1)
            
            for j in range(1, min(k+1, i+1)):
                
                M[i] = max(M[i], M[i-j] + max(arr[i-j+1:i+1]) * j)
            
        #print(M)
            
        return M[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        if k == 1:
            return sum(arr)
        
        if k == len(arr):
            max_val = max(arr)
            return max_val * len(arr)
        
        sums = [-1 for index in range(k)]
        maxs = [-1 for index in range(k)]
        max_sum = 0
        
        sums[0] = arr[0]
        maxs[0] = arr[0]
        
        for idx in range(1, len(arr)):
            val = arr[idx]
            max_sum = max(sums)
            for ki in range(k-1, 0, -1):
                max_val = maxs[ki-1]
                if not max_val < 0:
                    if val <= max_val:
                        maxs[ki] = max_val
                        sums[ki] = sums[ki-1] + max_val
                    else:
                        maxs[ki] = val
                        sums[ki] = sums[ki-1] - max_val * ki + val * (ki + 1)
            sums[0] = max_sum + val
            maxs[0] = val
        return max(sums)
        
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0]*n
        currMax = 0
        
        for i in range(n):
            if i < k:
                currMax = max(currMax,arr[i])
                dp[i] = currMax * (i+1)
            else:
                currMax = 0
                for j in range(1,k+1):
                    currMax = max(currMax,arr[i-j+1])
                    dp[i] = max(dp[i], dp[i-j]+currMax*j)
        return dp[n-1]
                    


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        '''Dynamic program using a list named dp, where dp[i] indicates the largest sum of the array arr[:i].'''
        dp = [0] * len(arr)
        for i in range(len(arr)):
            maxsum = 0
            for j in range(k):
                if i - j >= 1:
                    maxsum = max(maxsum, (j + 1) * max(arr[i - j: i + 1]) + dp[i - j - 1])
                elif i - j >= 0:
                    maxsum = max(maxsum, (j + 1) * max(arr[i - j: i + 1]))
            dp[i] = maxsum
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [float('-inf') for _ in range(n + 1)]
        dp[0] = 0
        
        for i in range(1, n + 1):
            j = i - 1
            cnt = k
            
            while j >= 0 and cnt >= 1:
                maximum = max(arr[j:i])
                dp[i] = max(dp[i], dp[j] + maximum*(i-j))
                j -= 1
                cnt -= 1
            
        return dp[-1]
        
        


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i, a in enumerate(A, 1):
            for j in range(1, K+1):
                # print(i, j, dp)
                if i-j >= 0:
                    dp[i] = max(dp[i], dp[i-j] + max(A[i-j:i])*j)
                else:
                    break
        # print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        # dp(i) = max array sum using elements up to index i
        # dp(i) = for j = 1 to k, find max of dp(i-j) + j * max(arr[i-j:i])
        
        dp = [0 for i in range(len(arr))]
        dp[0] = arr[0]
        
        for i in range(1, len(arr)):
            ans = 0
            for j in range(1, k+1):
                if i-j >= 0:
                    ans = max(ans, dp[i-j] + j * max(arr[i-j+1:i+1]))
                elif i-j == -1:
                    ans = max(ans, j * max(arr[i-j+1: i+1]))
                    
            dp[i] = ans
        
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
#don't really understand question. how did they partition exactly????        
        
        
        #dynamic programming! 
        #let d[i] be the answer for A[0]...A[i-1]
        ''' 
        S: d[i] be the answer for A[0]...A[i] answer = max sum of given array after partition. 
        R: want maximum of elements within K away from i. from hint 2:
        d[i] = d[i-j] + max{A[i-j],..., A[i]}*j, for j between 1 and k. 
        #times j because the max of that partition becomes the corresponding max for all            the positions in transformed A. 
        B = d[0]
        
        '''
        #base case:   

        #reference: https://leetcode.com/problems/partition-array-for-maximum-sum/discuss/783353/dp-with-python-and-some-comments-of-idea
        dp = [0]*(len(A)+1)
        for i in range(1, len(A)+1):
            temp = []
            for j in range(1, K+1): #go through all possible values of j
                if i - j >= 0:
                    k = dp[i-j] + max(A[i-j:i])*j
                    temp.append(k)
                    # print(k)
                    # dp[i] = max(k, dp[i]) 
                    #storing stuff in the same index so replacing it every time. 

            dp[i] = max(temp)
        return dp[len(A)]
            


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):
            for j in range(1, k+1):
                if (i-j)>=0:
                    dp[i]= max(dp[i], dp[i-j]+ max(arr[i-j:i])*j)
        
        
        return dp[n]
        
        


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0]
        for i in range(len(A)):
            curr = 0
            for j in range(i, max(-1, i - K), -1):
                curr = max(max(A[j: i + 1]) * (i - j + 1) + dp[j], curr)
            dp.append(curr)
        print(dp)
        return dp[-1]
                
                
                

                
    


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)
        # dp[i] is the answer for array A[0] ... A[i-1]
        # for j = 1 .. k, 
        #     dp[i] is the max of dp[i-j] + max(A[i-1] ... A[i-j]) * j
        
        # j = 1
        #         dp[i-1] + max(A[i-1]) * 1
        #         dp[i-2] + max(A[i-1], A[i-2]) * 2
        #         dp[i-3] + max(A[i-1], A[i-2], A[i-3]) * 3
        # ...
        #         dp[i-k] + max(A[i-1], ..., A[i-k]) * 3
        
        for i in range(1, n+1):
            for j in range(1, k+1):
                if i-j>=0:
                    dp[i] = max(dp[i], dp[i-j] + max(arr[i-j:i]) * j) # from i-j to i-1, with i-1-i+j+1 = j elements
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        dp=[0]*(n+1)
        for i in range(n):
            m=-1
            for j in range(1,k+1):
                if (i-j+1)<0:
                    break
                m=max(m,dp[i-j+1]+max(arr[i-j+1:i+1])*(j))
            dp[i+1]=m
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0 for _ in range(k + 1)]
        rolling_max = -1
        for i in range(0, k):
            rolling_max = max(rolling_max, arr[i])
            dp[i] = rolling_max * (i + 1)
        for i in range(k, len(arr)):
            rolling_max = arr[i]
            for j in range(1, k + 1):
                rolling_max = max(rolling_max, arr[i - j + 1])
                dp[i % (k + 1)] = max(rolling_max * j + dp[(i - j) % (k + 1)], dp[i % (k + 1)])
        return dp[(len(arr) - 1) % (k + 1)]

# 10:28 -> misunderstood the problem
# dp
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0 for num in arr]
        for i in range(len(arr)):
            prev_sum = 0 if i - 1 < 0 else dp[i - 1]
            max_at_i = arr[i] + prev_sum
            possible_ks = i if i < k - 1 else k - 1
            for j in range(1, possible_ks + 1):
                current_window = arr[i - j: i + 1]
                current_max = max(current_window)
                current_window_sum = len(current_window) * current_max
                prev_window_sum = 0 if i - j - 1 < 0 else dp[i - j - 1]
                total_sum = current_window_sum + prev_window_sum
                if total_sum > max_at_i:
                    max_at_i = total_sum
            dp[i] = max_at_i
            # print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        L=len(arr)
        record=dict()
        record[0]=0
        for idx in range(1,L+1):
            r=-float('inf')
            for gap in range(1,k+1):
                if idx-gap<0:
                    continue
                else:
                    r=max(r,max(arr[idx-gap:idx])*gap+record[idx-gap])
            record[idx]=r
        return record[L]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i, a in enumerate(A, 1):
            for j in range(1, K+1):
                # print(i, j, dp)
                if i-j >= 0:
                    dp[i] = max(dp[i], dp[i-j] + max(A[i-j:i])*j)
        # print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr) + 1)
        dp[0] = 0
        for i in range(len(arr)):
            dp[i+1] = dp[i] + arr[i]
            for j in range(k, 1, -1):
                if i-j+1 >= 0:
                    dp[i+1] = max(dp[i+1], dp[i-j+1] + max(arr[i-j+1:i+1]) * j)
        # print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        hashmap = {}
        def partitionMatrix(lst, currScore):
            key = tuple(lst)
            if key in hashmap:
                return hashmap[key] + currScore
            if lst == []:
                hashmap[key] = 0
                return currScore
            for i in range(1, k + 1):
                if len(lst) == i:
                    hashmap[key] = (max(lst) * i)
                    return currScore + (max(lst) * i)
            best = currScore
            for i in range(1, k + 1):
                subScore = max(lst[:i]) * i
                best = max(best, partitionMatrix(lst[i:], currScore + subScore))
            hashmap[key] = best - currScore
            return best
        return partitionMatrix(arr, 0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp=[0]*(len(arr)+1)
        dp[1]=arr[0]
        for i in range(1,len(arr)):
            for j  in range(max(0,i-k+1),i+1):
                dp[i+1]=max(dp[i+1],dp[j]+max(arr[j:i+1])*(i-j+1))
                
            
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [[0 for _ in range(len(A))] for _ in range(2)]
        
        dp2 = [0 for _ in range(len(A))]
        
        for i in range(len(A)):
            # we have 2 options - to partition or not to partition.
            
#             if i - K + 1 < 0:
#                 maxCand = max(A[:i+1])
#                 size = i + 1
#             else:
#                 maxCand = max(A[i - K + 1:i+1])
#                 size = K
                
#             # if we choose not to partition
#             dp[0][i] = size * maxCand + max(dp[0][i - K], dp[1][i - K])
            
#             # if we choose to partition at this candidate
#             dp[1][i] = A[i] + max(dp[0][i - 1], dp[1][i - 1])

            startIndex = max(0, i - K + 1)
    
            while startIndex <= i:
                if startIndex - 1 >= 0:
                    dp2[i] = max(dp2[startIndex - 1] + max(A[startIndex:i+1])*(i + 1 - startIndex), dp2[i])
                else:
                    dp2[i] = max(A[:i+1]) * (i + 1)
                    
                startIndex += 1
                    
        print(dp2)   
        return dp2[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        # 
        def rec(l,h):
            if h-l<K:
                dp[l][h] = (h-l+1)*max(A[l:h+1])
                return dp[l][h]
            m = []
            if dp[l][h]>0:
                return dp[l][h]
            for i in range(0,K):
                m += [rec(l,l+i) + rec(l+i+1,h)]
            dp[l][h] = max(m)
            return dp[l][h]
        
        dp = [0]*len(A)
        dp = [[0]*len(A) for i in range(len(A))]
        
        rec(0,len(A)-1)
        
        return dp[0][len(A)-1]


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

        for i in range(size):
            mem[i] = arr[i]
            for j in range(0, k):
                if i - j > 0:
                    candidate = max(arr[i - j: i + 1]) * (j + 1) + mem[i - j - 1]
                    mem[i] = max(mem[i], candidate)
                elif i - j == 0:
                    candidate = max(arr[i - j: i + 1]) * (j + 1)
                    mem[i] = max(mem[i], candidate)
                else:
                    break
        return mem[size - 1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        A = arr
        dp = [0] * (n := len(arr))
        dp[0] = curr_max = arr[0]
        
        for i in range(1, k):
            curr_max = max(curr_max, A[i])
            dp[i] = (i + 1) * curr_max
        
        for i in range(k, n):
            curr_max = A[i]
            for j in range(k):
                curr_max = max(curr_max, A[i - j])
                dp[i] = max(dp[i], dp[i - j - 1] + curr_max * (j + 1))
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0]
        for i in range(len(arr)):
            max_sum = -float('inf')
            for j in range(1, k+1):
                if i - j + 1 < 0:
                    break
                max_sum = max(max_sum, max(arr[i-j + 1: i+1]) * j + dp[i - j + 1])
            dp.append(max_sum)
        return dp[-1]

class Solution:
    def getMax(self, arr, k, idx, cache):
        # I am partitioning 1 element
        if idx == len(arr) - 1:
            return arr[idx]
        # I need to get max sum after partitioning
        maxSum = 0
        
        # [1,2,9,30]
        # I need to try partitioning from 1 -> K elements
        for numInPartition in range(1, k + 1):
            # I cannot choose elements if I would be choosing too many elements
            if idx + numInPartition > len(arr):
                break
            
            startOfRecursiveIndex = idx + numInPartition
            # select max value in first 'k' elements
            maxVal = max(arr[idx:startOfRecursiveIndex])
            
            # generates sum for this subset
            partSum = maxVal * numInPartition
            
            # I need to get the partition sum for the rest of the elements
            
            rest = cache[startOfRecursiveIndex] if startOfRecursiveIndex in cache else self.getMax(arr, k, startOfRecursiveIndex, cache)
            
            cache[startOfRecursiveIndex] = rest
            
            maxSum = max(maxSum, partSum + rest)
        return maxSum
            
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        '''
        Input:
            A: int[] - Array of numbers
            K: int - Max length allowable for subarray
            
        Output:
            Return largest sum after partitioning.
        
        Steps:
            1. Make partition
            2. Change all elements to max value
            
           v            
        [1,2,9,30], 2
        
        {1,2}{9,30} => {2,2}{30,30} => 4 + 60 = 64
        {1}{2,9}{30} => {1}{9,9}{30} => 1 + 18 + 30 = 49
        
        
        Example:
            [1]
            {1} = 1
            
            [1,2]
            {1}{2} => 1+2 = 3
            {1,2} => {2,2} => 4
                 v
            [1,2,9]
            {1,2}{9} => {2,2} + {9} => 4 + 9 = 13
            {1}{2,9} => {1},{9,9} = 1 + 18 = 19
            {1,2,9}
            
            {1}{2,9}{30} => {1}{9,9}{30} => 19 + 30 => 49
            {1,2}{9,30} => {2,2}{30,30} => 4 + 60 => 64
            
                 v
            [1,2,9,30]
            {1,2,9} {30} => 30 + getMaxSum([1,2,9]) => 30 + 19 => 49
            {1,2} {9,30} => 60 + getMaxSum([1,2]) => 60 + 4 = 64
            
            {1}{2,9,30}
            {1,2}{9,30}
            {1,2,9}{30}
        
        All about subproblems!!
        
        Approach:
            - Let's look into sliding window.
            - We can frame this problem in terms of choices.
                When considering an element, we can place it into its own partition OR with the preceeding partition.
                Choice:
                    K-way choice
                    Do I group my current element in the last [1,k] elements?
                Constraint:
                    Subset needs to be contiguous?
                Goal:
                    Maximum sum
                
            1. When placing
        Approach:
            [0,0,0,0]
            maxSum[i] = max(maxSum[i-1] + A[i] * 1, maxSum[i-2] + max(last two elements) * 2) and so on
        '''
        
        cache = {}
        return self.getMax(A, K, 0, cache)
       
    
    
    
    


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        mem = {}
        
        def find(s, e):
            if (s,e) in mem:
                return mem[(s,e)]
            
            if e-s == 1:
                return arr[s]
            elif e-s == 0:
                return 0
            else:
                m = None
                for i in range(s+1, min(s+k+1, len(arr)+1)):
                    subsum = max(arr[s:i])*(i-s) + find(i,e)
                    if m is None or subsum > m:
                        m = subsum
                mem[(s,e)] = m
                return m
            
        return find(0, len(arr))

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        if not arr:
            return 0
        n = len(arr)
        dp = [0] * n
        for i in range(n):
            for j in range(k):
                if i - j < 0:
                    continue
                _max = max(arr[i-j : i+1])
                _sum = _max * (j+1) if i-j == 0 else dp[i-j-1] + _max*(j+1)
                dp[i] = max(dp[i], _sum)
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [nums[0]] + [0] * (n - 1)
        for i in range(1, n):
            for j in range(max(0, i - k + 1), i + 1):
                dp[i] = max(dp[i], dp[j - 1] + max(nums[j:i + 1]) * (i + 1 - j))
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        from functools import lru_cache
        @lru_cache(None)        
        def dp(i):
            ans=0
            for k in range(K):
                if i-k>=0:
                    ans=max(ans,max(A[i-k:i+1])*(k+1)+dp(i-k-1))
                    
            return ans
        
        return dp(len(A)-1)

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

        for i in range(n):
            for j in range(k):
                if i-j < 0:
                    continue
                _max = max(arr[i-j:i+1])
                _sum = _max*(j+1) if i-j == 0 else dp[i-j-1] + _max*(j+1)
                dp[i] = max(dp[i], _sum)

        return dp[-1]



class Solution:
    def maxSumAfterPartitioning(self, arr, k):
        if not arr:
            return 0
        
        dp = [0]*len(arr)
        
        for i in range(len(arr)):
            for j in range(k):
                if i-j < 0 :
                    continue
                max_val = max(arr[i-j : i+1])
                if i-j == 0:
                    total = max_val * (j+1)
                else:
                    total = dp[i-j-1] + max_val * (j+1)
                dp[i] = max(dp[i], total)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0] * N
        dp[0] = A[0]

        for i in range(1, N):
            for j in range(0, min(K, i+1)):
                current_subarray = A[i-j:i+1]
                if i >= K:
                    dp[i] = max(dp[i], dp[i-j-1] + max(current_subarray)*(j+1))
                else:
                    dp[i] = max(dp[i], max(current_subarray)*(j+1))
            
        return dp[-1]
            
            
        # [1,15,7,9,2,5,10] k = 3
        # No need to inspect all combination, focus on growth
        
        # (1)
        # [1] -> 1 - max(A[i])*1
        
        # (1,15)
        # [1,15] -> 30 - max(A[i-1], A[i])*2
        # [1][15] -> 16 - DP[i-1] + A[i]
        
        0,1
        1,1
        
        # (1,15,7)
        # [1,15,7] -> 45 max(A[i]. A[i-1], A[-2])*3
        # [1][15,7] -> 23 - DP[i-2] + max(A[i-1], A[i])*2
        # [1,15][7] -> 37 - DP[i-1] + A[i]
        
        # (1,15,7,9)
        # [1,15,7][9] -> 54 DP[i-1] + A[i]
        # [1,15][7,9] -> 32 DP[i-2] + max(A[i-1], A[i])*2
        # [1][15,7,9] -> 46 DP[i-3] + max(A[i-2], A[i-1], A[i])*3
        


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * n
        for i in range(n):
            if i == 0:
                dp[i] = A[0]
            else:
                # A[i-k+1, ..., i-1, i] is a subarray
                # A[0, 1, 2, ..., i-k] is previous chuck with subarray length up to K
                for k in range(1, K+1):
                    if i-k+1 < 0:
                        break
                    elif i-k+1 == 0:
                        dp[i] = max(dp[i], max(A[i-k+1:i+1]) * k)
                    else:
                        dp[i] = max(dp[i], dp[i-k] + max(A[i-k+1:i+1]) * k)
        return dp[n-1]


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

        for i in range(n):
            for j in range(k):
                if i-j < 0:
                    continue
                _max = max(arr[i-j:i+1])
                _sum = _max*(j+1) if i-j == 0 else dp[i-j-1] + _max*(j+1)
                dp[i] = max(dp[i], _sum)

        return dp[-1]

class Solution:
    
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        n = len(A)
        dp = [0] * (n + 1)
        
        for i in range(n):
            for k in range(1,K+1):
                if i-k > -2: dp[i+1] = max(dp[i+1], max(A[max(0,i-k+1):i+1]) * k + dp[i+1-k])
                
        return dp[n]

class Solution:
    
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        n = len(A)
        dp = [0] * (n + 1)
        
        for i in range(n):
            dp_ix = i+1
            for k in range(1,K+1):
                if i-k > -2:
                    dp[dp_ix] = max(dp[dp_ix], max(A[max(0,i-k+1):i+1]) * k + dp[dp_ix-k])
                
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [[0 for _ in range(len(A))] for _ in range(2)]
        
        dp2 = [0 for _ in range(len(A))]
        
        for i in range(len(A)):
            # we have 2 options - to partition or not to partition.
            
#             if i - K + 1 < 0:
#                 maxCand = max(A[:i+1])
#                 size = i + 1
#             else:
#                 maxCand = max(A[i - K + 1:i+1])
#                 size = K
                
#             # if we choose not to partition
#             dp[0][i] = size * maxCand + max(dp[0][i - K], dp[1][i - K])
            
#             # if we choose to partition at this candidate
#             dp[1][i] = A[i] + max(dp[0][i - 1], dp[1][i - 1])

            startIndex = max(0, i - K + 1)
            currMax = 0
            while startIndex <= i:
                currMax = max(currMax, A[startIndex])
                if startIndex - 1 >= 0:
                    dp2[i] = max(dp2[startIndex - 1] + max(A[startIndex:i+1])*(i + 1 - startIndex), dp2[i])
                else:
                    dp2[i] = max(A[:i+1]) * (i + 1)
                    
                startIndex += 1
                    
        print(dp2)   
        return dp2[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * len(arr)
        
        for i in range(len(arr)):
            print(arr[i])
            max_so_far = arr[i] + (dp[i-1] if i > 0 else 0)
            for j in range(1, min(i+1, k)):
                max_in_range = max(arr[i-j:i+1])
                max_so_far = max(max_so_far, dp[i-j-1] + max_in_range * (j+1))
            dp[i] = max_so_far
        return dp[len(arr)-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr))
        dp[0] = arr[0]
        for i,val in enumerate(arr):
            if i == 0: continue
            cur_max = val + dp[i-1]
            cur_k = 1
            while(i-cur_k>=0 and cur_k < k):
                temp = arr[i-cur_k:i+1]
                m = max(temp)
                if i-cur_k==0: cur_max = max(cur_max, m* (cur_k+1) )
                else:
                    cur_max = max(cur_max,( m * (cur_k+1)) + dp[i-cur_k-1] )
                cur_k += 1
            dp[i] = cur_max
        return dp[-1]
            
        '''    
        #[1,4,1, 5, 7, 3, 6, 1, 9, 9, 3]
        # 1 5
        
        
        
        
        
        
        '''

        
        
        
        
        
        
        
        
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        DP = [0 for _ in range(len(arr)+1)]
        for i in range(1,len(DP)):
            loc = max(i-k,0)
            run_max = 0
            for j in range(loc,i):
                run_max = max(run_max,DP[j]+max(arr[j:i])*(i-j))
            DP[i] = run_max
        return DP[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        if not K or K == 1:
            return sum(A)
        if not A:
            return 0

        dp = [0] * len(A)
        for index, num in enumerate(A):
            possible = []
            for group in range(K):
                if index - group >= 0:
                    if index - group - 1 >= 0:
                        previous = dp[index - group - 1]
                    else:
                        previous = 0
                    possible.append(
                        previous + max(A[index - group : index + 1]) * (group + 1)
                    )

            dp[index] = max(possible)
            # print(f\"{index=} {dp[index]=}\")
        return dp[-1]


class Solution:
    
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        self.arr = arr
        self.dp = {}
        
        def helper(i,j,k):
            
            if j <= i:
                return 0
            
            if (i,j) in self.dp:
                return self.dp[(i,j)]
            
            maxsum = -sys.maxsize
            
            for length in range(1,k+1):
                
                if i+length <= j:
                    
                    currsum = (max(self.arr[i:i+length]) * length) + helper(i+length,j,k)
                    maxsum = max(maxsum,currsum)
            
            self.dp[(i,j)] = maxsum
            return self.dp[(i,j)]
        
        return helper(0,len(arr),k)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        
        dp=[0 for _ in A]
        
        for i,num in enumerate(A):
            for j in range(K):
                ans=0            
                if i-j>=0:
                    ans = ans + (j+1)*max(A[i-j:i+1])
                if i-j-1>=0:
                    ans = ans + dp[i-j-1]
                dp[i]=max(dp[i],ans)
                
                
#                 if i-p-1>=0:
#                     ans=dp[i-p-1]+(p+1)*max(A[i-p:i+1])
#                     print(A[i-p-1],(p+1)*max(A[i-p:i+1]))
#                     dp[i]=max(dp[i],ans)
        
        #print(dp)
        
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        d = [0] * (1 + len(arr) + k)
        for ind in range(1, len(arr) + 1):
            for sub_arr_st in range(min(ind, k)):
                if arr[ind - sub_arr_st - 1] > arr[ind - 1]:
                    break
                for sub_arr_len in range(sub_arr_st + 1, k + 1):
                    ind_x = ind - sub_arr_st + sub_arr_len - 1
                    d[ind_x] = max(d[ind_x], d[ind - sub_arr_st - 1] + arr[ind - 1] * sub_arr_len)
        return d[len(arr)]

class Solution:
    
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp=[0]*(len(arr)+1)
        dp[0]=arr[0]
        for i in range(1,len(arr)):
            ans=-100000
            for z in range(max(0,i-k+1) ,  i+1):
                # print(z,i+1)
                ans=max(dp[z-1]+max(arr[z:i+1])*(i-z+1) , ans)
                # ans=max(dp[i-z-1]+max(arr[i-z-1:i+1])*(z+1),ans)
            dp[i]=ans
        return dp[-2]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        cacheMax=[[0]*len(arr) for i in range(len(arr))]
        for i in range(len(arr)):
            cacheMax[i][i]=arr[i]
        for i in range(1,len(arr)):
            for j in range(i):
                cacheMax[j][i] = max(cacheMax[j][i-1],arr[i])
        
        
        
        
        dp=[0]*(len(arr)+1)
        dp[1]=arr[0]
        for i in range(1,len(arr)):
            for j  in range(max(0,i-k+1),i+1):
                dp[i+1]=max(dp[i+1],dp[j]+max(arr[j:i+1])*(i-j+1))
                
            
        return dp[-1]

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

        l_arr = len(arr)

        for chain_len in range(0, k, 1):
            for i in range(0, l_arr - chain_len, 1):
                memo[(i, i + chain_len)] = max(arr[i : i + chain_len + 1]) * (chain_len + 1)
        res_memo = {}    

        def dfs(idx):
            if idx == l_arr:
                return 0

            if idx in res_memo:
                return res_memo[idx]

            res_memo[idx] = max( memo[(idx, idx + j)] + dfs(idx + j + 1) for j in range(k) if idx + j < l_arr )
            return res_memo[idx]

        return dfs(0)

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        # use dp to solve this question
        n = len(A)
        dp = [0] * (n + 1)
        # dp[i] is the answer for array A[0] ... A[i-1]
        # for j = 1 .. k, 
        #     dp[i] is the max of dp[i-j] + max(A[i-1] ... A[i-j]) * j
        
        # j = 1
        #         dp[i-1] + max(A[i-1]) * 1
        #         dp[i-2] + max(A[i-1], A[i-2]) * 2
        #         dp[i-3] + max(A[i-1], A[i-2], A[i-3]) * 3
        # ...
        #         dp[i-k] + max(A[i-1], ..., A[i-k]) * 3
        
        for i in range(1, n+1):
            for j in range(1, K+1):
                if i-j>=0:
                    dp[i] = max(dp[i], dp[i-j] + max(A[i-j:i]) * j) # from i-j to i-1, with i-1-i+j+1 = j elements
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0 for i in range(len(A)+1)]
        for i in range(1, len(A)+1):
            dp[i] = max([dp[i-j] + j * max(A[i-j:i]) for j in range(1, K+1) if j <= i])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        res = [0] * (len(arr) + 1)
        
        for i in range(1, len(arr) + 1):
            for j in range(1, k + 1):
                if i - j > -1:
                    res[i] = max(res[i], res[i - j] + max(arr[i - j : i]) * j)
        
        return res[-1] 

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        ar_len = len(arr)
        dp= [0] * (ar_len+1)
        for i in range(1,len(dp)):
            tmp_max = []
            for j in range(1,k+1):
                if i-j >=0:
                    max_t = dp[i-j] + max(arr[i-j:i]) * j
                    tmp_max.append(max_t)
            dp[i] = max(tmp_max)
            
        return dp[-1]
                


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        if k == n: return n * max(arr)
        dp = collections.deque([0] * k)
        for i in range(n - 1, -1, -1):
            m = 0
            result = 0
            for j in range(min(k, n - i)):
                m = max(m, arr[i + j])
                result = max(result, m * (j + 1) + dp[j])
            dp.appendleft(result)
            dp.pop()
        return dp[0]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0] * N
        dp[0] = A[0]
        #print('DP:', dp)
        #print()
        for i in range(1, N):
            for j in range(0, min(K, i+1)):
                current_subarray = A[i-j:i+1]
                #print( max(current_subarray)*(j+1), current_subarray, i, j)
                if i >= K:
                    dp[i] = max(dp[i], dp[i-j-1] + max(current_subarray)*(j+1))
                else:
                    dp[i] = max(dp[i], max(current_subarray)*(j+1))
            
            
            #print('DP:', dp)
            #print()
            
        return dp[-1]
            
            
        # [1,15,7,9,2,5,10] k = 3
        # No need to inspect all combination, focus on growth
        
        # (1)
        # [1] -> 1 - max(A[i])*1
        
        # (1,15)
        # [1,15] -> 30 - max(A[i-1], A[i])*2
        # [1][15] -> 16 - DP[i-1] + A[i]
        
        0,1
        1,1
        
        # (1,15,7)
        # [1,15,7] -> 45 max(A[i]. A[i-1], A[-2])*3
        # [1][15,7] -> 23 - DP[i-2] + max(A[i-1], A[i])*2
        # [1,15][7] -> 37 - DP[i-1] + A[i]
        
        # (1,15,7,9)
        # [1,15,7][9] -> 54 DP[i-1] + A[i]
        # [1,15][7,9] -> 32 DP[i-2] + max(A[i-1], A[i])*2
        # [1][15,7,9] -> 46 DP[i-3] + max(A[i-2], A[i-1], A[i])*3
        
        
        
        
        
        
        
                # N = len(A)
        # dp = [0] * (N + 1)
        # for i in range(N):
        #     curMax = 0
        #     for k in range(1, min(K, i + 1) + 1):
        #         curMax = max(curMax, A[i - k + 1])
        #         dp[i] = max(dp[i], dp[i - k] + curMax * k)
        #         print(dp)
        #     print()
        # return dp[N - 1]


class Solution:
    def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
        '''
        
               v
        [1,30,45,_,_,_,_,????]
        [1,15,7, 9,2,5,10], 2
        
        dp[i] = max( (windowSize * maxInWindow) + dp[i - windowSize] ) for valid windowSize from 1 to k
        
        return dp[-1]
        
        30 + [7] => 37
        1  + [15,7] => 31
        0  + [1,15,7] => 45 <<<<<
        [1,15]
        '''
        
        dp = [0] * len(nums)
        
        for i in range(len(nums)):
            
            # generate all window sizes
            # [1,2,3]
            # if k = 3
            for windowSize in range(1, k + 1):
                startIndex = i - windowSize + 1
                
                # Bounding Function to make sure that I don't run out of bounds
                if startIndex < 0:
                    break
                
                #         v
                #           v 
                # # [1,15,7,9,2,5,10]
                
                maxVal = max(nums[startIndex: i + 1])
                
                currVal = windowSize * maxVal
                
                
                currSum = currVal
                
                if startIndex > 0:
                    currSum += dp[startIndex - 1]
                    
                dp[i] = max(dp[i], currSum)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        memo = {n:0}
        def helper(arr, i):
            if i in memo:
                return memo[i]
            res = 0
            for j in range(i, min(n,i+k)):
                res = max(res, helper(arr, j+1)+max(arr[i:j+1])*(j+1-i))
            memo[i] = res
            return res
        return helper(arr, 0)

class Solution:
    def maxSumAfterPartitioning(self, nums: List[int], k: int) -> int:
        '''
        
               v
        [1,30,45,_,_,_,_,????]
        [1,15,7, 9,2,5,10], 2
        
        dp[i] = max( (windowSize * maxInWindow) + dp[i - windowSize] ) for valid windowSize from 1 to k
        
        return dp[-1]
        
        30 + [7] => 37
        1  + [15,7] => 31
        0  + [1,15,7] => 45 <<<<<
        [1,15]
        '''
        
        dp = [0] * len(nums)
        
        for i in range(len(nums)):
            
            # generate all window sizes
            # [1,2,3]
            # if k = 3
            for windowSize in range(1, k + 1):
                startIndex = i - windowSize + 1
                
                # Bounding Function to make sure that I don't run out of bounds
                if startIndex < 0:
                    break
                
                #         v
                #           v 
                # # [1,15,7,9,2,5,10]
                
                maxVal = max(nums[startIndex: i + 1])
                
                currVal = windowSize * maxVal
                
                
                currSum = currVal
                
                if startIndex > 0:
                    currSum += dp[startIndex - 1]
                    
                dp[i] = max(dp[i], currSum)
        print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0 for i in range(len(A)+1)]
        for i in range(1, len(A)+1):
            dp[i] = max([dp[i-j] + j * max(A[i-j:i]) for j in range(1, K+1) if j <= i])
        print(dp)
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * len(arr)
        
        for i in range(len(arr)):
            max_so_far = arr[i] + (dp[i-1] if i > 0 else 0)
            for j in range(1, min(i+1, k)):
                max_in_range = max(arr[i-j:i+1])
                max_so_far = max(max_so_far, dp[i-j-1] + max_in_range * (j+1))
            dp[i] = max_so_far
        return dp[len(arr)-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        result = [0]*len(arr)
        result[0] = arr[0]
        max_val = result[0]
        for i in range(1,k):
            max_val = max(max_val,arr[i])
            result[i] = max_val*(i+1)
        #print(result)
        for i in range(k,len(arr)):
            max_val = arr[i]
            for j in range(1,k+1):
                max_val = max(max_val,arr[i-j+1])
                result[i] = max(result[i],result[i-j]+max_val*j)
                #print(i,j,max_val,result[i])
        #print(result)
        return result[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        A = arr
        
        K = k
        
        n = len(A)
        dp = [0] * n
        curMax = 0
        for i in range(n):
            if i < K: 
                curMax = max(curMax, A[i])
                dp[i] = curMax * (i + 1)
            else:
                curMax = 0
                for j in range(1, K + 1):
                    curMax = max(A[i - j + 1], curMax)
                    dp[i] = max(dp[i], dp[i - j] + curMax * j)
                    
                    
        # print(dp)
        
        return dp[n - 1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        if not arr:
            return 0
        n = len(arr)
        dp = [0] * n
        curr_max = arr[0]
        for i in range(k):
            curr_max = max(curr_max, arr[i])
            dp[i] = curr_max * (i + 1)
        
        for i in range(k, n):
            dp[i] = arr[i]
            curr_max = arr[i]
            for j in range(k):
                curr_max = max(curr_max, arr[i-j])
                dp[i] = max(dp[i], dp[i-j-1] + curr_max * (j + 1))
        return dp[-1]
            
        
        # @lru_cache(None)
        # def dp(idx):
        #     if idx < 0:
        #         return 0
        #     left = max(0, idx - k + 1)
        #     curr_max = arr[idx]
        #     res = arr[idx]
        #     for i in range(idx, left - 1, -1):
        #         curr_max = max(curr_max, arr[i])
        #         res = max(res, dp(i-1) + curr_max * (idx - i + 1))
        #     return res
        # return dp(len(arr)-1)


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 = float('-inf')
            for j in range(1, min(i, k)+1):
                max_val = max(max_val, arr[i-j])
                dp[i] = max(dp[i], dp[i-j] + j*max_val)
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp=[0]*len(arr)
        dp[0]=arr[0]
        max1=arr[0]
        for i in range(1,k):
            max1=max(max1,arr[i])
            dp[i]=max1*(i+1)
     
        for i in range(k,len(arr)):
            max1=arr[i]
           
            for j in range(1,k+1):
                dp[i]=max(dp[i],max1*j+dp[i-j])
                max1=max(arr[i-j],max1)
        return dp[-1]

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

        f = [0]
        for end in range(1, len(arr)+1):
            _local = 0
            _cur_max = 0
            for start in range(end-1, max(0, end-k)-1, -1):
                _cur_max = max(_cur_max, arr[start])
                _local = max(_cur_max *(end - start)+f[start], _local)
                
                
            f.append(_local)
        return f[-1]
    
        


class Solution:
    def maxSumAfterPartitioning(self, arr, k):
        n = len(arr)
        dp = [0]*(n+1)
        for i in range(n):
            cmax = 0
            for j in range(1, min(k, i+1) + 1):
                cmax = max(cmax, arr[i-j+1])
                dp[i] = max(dp[i], dp[i-j] + cmax*j)
        return dp[-2]
                
        


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)
        for i in range(n):
            curMax = 0
            for j in range(1, min(k, i + 1) + 1):
                curMax = max(curMax, arr[i - j + 1])
                dp[i] = max(dp[i], dp[i - j] + curMax * j)
        return dp[n - 1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        best_sums = [0] * (len(arr)+1)
        for i in range(len(arr)):
            curr_max = 0
            for j in range(1,min(k+1,i+2)):
                curr_max = max(curr_max, arr[i-j+1])
                best_sums[i] = max(best_sums[i], best_sums[i-j] + j*curr_max)
        return best_sums[-2]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        DP=[0]*len(arr)
        N=len(arr)
        DP[0]=arr[0]
        m=arr[0]
        for i in range(k):
            m=max(m,arr[i])
            DP[i]=m*(i+1)
            
      #  print(DP)
        for i in range(k,N):
            mm=arr[i]
            DP[i]=DP[i-1]+arr[i]
        #    print(DP[i],i)
          #  print(i,DP,mm,arr[i])
            for j in range(1,k):
                mm=max(mm,arr[i-j])
             #   print(i,mm,arr[i-j],DP[i-j])
                DP[i]=max(DP[i],DP[i-j-1]+mm*(j+1))
            #DP[i]=max(DP[i-1]+arr)
    #    print(DP)
        return DP[-1]
  #  [5,7,7,7,7]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        dp=[0]*(n+1)
        
        
        for i in range(n):
            cur=0
            for j in range(1,min(k,i+1)+1):
                cur=max(cur,arr[i-j+1])
                dp[i]=max(dp[i],cur*j+dp[i-j])
        return dp[-2]
                


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)
        
        for i in range(n):
            cur_max = 0
            for j in range(1, min(k, i + 1) + 1):
                cur_max = max(cur_max, arr[i - j + 1])
                dp[i] = max(dp[i], dp[i - j] + cur_max * j)
                
        return dp[n - 1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        @lru_cache(None)
        def dp(idx):
            if idx < 0:
                return 0
            left = max(idx - k + 1, 0)
            curr_max = arr[idx]
            res = arr[idx]
            for i in range(idx, left - 1, -1):
                curr_max = max(curr_max, arr[i])
                res = max(res, dp(i-1) + (idx - i + 1) * curr_max)
            return res
        # print(dp(3))
        return dp(len(arr) - 1)
        
        # A = arr
        # dp = [0] * (n := len(arr))
        # dp[0] = curr_max = arr[0]
        # for i in range(1, k):
        #     curr_max = max(curr_max, A[i])
        #     dp[i] = (i + 1) * curr_max
        # for i in range(k, n):
        #     curr_max = A[i]
        #     for j in range(k):
        #         curr_max = max(curr_max, A[i-j])
        #         dp[i] = max(dp[i], dp[i-j-1] + curr_max * (j + 1))
        # return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:        
        N = len(arr)
        dp = [0] * (N+1)
        for i in range(N):
            cur_max = 0
            for j in range(1, min(k, i+1)+1):
                cur_max = max(cur_max, arr[i-j+1]) # 从当前元素开始
                dp[i] = max(dp[i], dp[i-j]+cur_max*j)
        return dp[N-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        # O(NK) coming sooooon

        N = len(arr)
        dp = [0 for _ in range(N)] 

        dp[0] = arr[0]
        max_so_far = arr[0]
        for i in range(1, k):
            max_so_far = max(max_so_far, arr[i])
            dp[i] = (i+1) * max_so_far
        
        # now the actual thing
        for i in range(k, N):
            max_so_far = -sys.maxsize

            for j in range(i, i-k, -1):
                max_so_far = max(max_so_far, arr[j])
                dp[i] = max(dp[i], dp[j-1] + (i-j+1) * max_so_far)
        
        return dp[N-1]



class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            max_val = float('-inf')
            for w in range(1, K + 1):
                if i - w < 0: break
                max_val = max(max_val, A[i - w])
                dp[i] = max(dp[i], dp[i - w] + max_val * w)
            
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            cur = 0
            for j in range(1, K + 1):
                if i >= j:
                    cur = max(cur, A[i - j])
                    dp[i] = max(dp[i], dp[i - j] + cur * j)
        return dp[n]

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):
            j = i - 1
            mx = -float('inf')
            while i - j <= k and j >= 0:
                mx = max(mx,arr[j])
                dp[i] = max(dp[i],dp[j]+mx * (i - j))
                j -= 1
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        n = len(A)
        dp = [0] * (n+1)
        for i in range(1,n+1):
            j = i - 1
            mx = -float('inf')
            while i - j <= K and j >= 0:
                mx = max(mx,A[j])
                dp[i] = max(dp[i],dp[j]+mx * (i - j))
                j -= 1
        return dp[n]



class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr)+1)
        for i in range(1, len(dp)):
            maxone = 0
            for j in range(i, i-k, -1):
                if j >= 1:
                    maxone = max(maxone, arr[j-1])
                    dp[i] = max(dp[i], dp[j-1]+maxone * (i-j+1))
        return dp[-1]

class Solution:     
    def maxSumAfterPartitioning(self, A, K):
        N = len(A)
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i + 1) + 1):
                curMax = max(curMax, A[i - k + 1])
                dp[i] = max(dp[i], dp[i - k] + curMax * k)
        return dp[N - 1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        DP = [0]*(N+1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i+1) + 1):
                curMax = max(curMax, A[i-k+1])
                DP[i] = max(DP[i], DP[i-k] + curMax * k)
        return DP[N-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n+1)
        for i in range(n):
            cur_max = 0
            for d in range(1, min(k, i+1)+1):
                cur_max = max(cur_max, arr[i-d+1])
                dp[i+1] = max(dp[i+1], dp[i+1-d] + cur_max * d) 
            # print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n=len(arr)
        dp=[0]*(n+1)
        for i in range(n):
            m=-1
            x=-1
            for j in range(1,k+1):
                if (i-j+1)<0:
                    break
                x=max(x,arr[i-j+1])
                m=max(m,dp[i-j+1]+x*j)
            dp[i+1]=m
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0 for _ in arr]
        rolling_max = -1
        for i in range(0, k):
            rolling_max = max(rolling_max, arr[i])
            dp[i] = rolling_max * (i + 1)
        for i in range(k, len(arr)):
            rolling_max = arr[i]
            for j in range(1, k + 1):
                rolling_max = max(rolling_max, arr[i - j + 1])
                dp[i] = max(rolling_max * j + dp[i - j], dp[i])
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0]
        for i in range(1, len(arr) + 1) :
            max_arr_num = 0
            now_max = 0
            for j in range(1, k + 1) :
                idx = i - j
                if idx >= 0 :
                    max_arr_num = max(max_arr_num, arr[idx])
                    now_max = max(now_max, dp[idx] + max_arr_num * j)
            dp.append(now_max)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [0] * (n+1)
        for i in range(1,n+1):
            m = float('-inf')
            for j in range(1,K+1):
                if i - j >= 0:
                    m = max(A[i-j],m)
                    dp[i] = max(dp[i],dp[i-j] + m*j)
        return dp[-1]
        
        
        # n = len(A)
        # dp = [0] * (n+1)
        # for i in range(1,n+1):
        #     m = float('-inf')
        #     for j in range(1,K+1):
        #         if i - j >= 0:
        #             m = max(A[i-j],m)
        #             dp[i] = max(dp[i],dp[i-j]+m*j)
        # return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        
        dp = [0] * (n+1)
        res = 0 
        for i in range(n):
            max_val = 0
            for k in range(1, min(K, i+1)+1):
                max_val = max(max_val, A[i-k+1])
                dp[i] = max(dp[i], dp[i-k] + max_val*k)
        return dp[n-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0] * (len(arr))
        dp[0] = arr[0]
        for i,val in enumerate(arr):
            if i == 0: continue
            cur_max = val + dp[i-1]
            cur_k = 1
            m = val
            while(i-cur_k>=0 and cur_k < k):
                # temp = arr[i-cur_k:i+1]
                m = max(m,arr[i-cur_k])
                if i-cur_k==0: cur_max = max(cur_max, m* (cur_k+1) )
                else:
                    cur_max = max(cur_max,( m * (cur_k+1)) + dp[i-cur_k-1] )
                cur_k += 1
            dp[i] = cur_max
        return dp[-1]
            
        '''    
        #[1,4,1, 5, 7, 3, 6, 1, 9, 9, 3]
        # 1 5
        
        
        
        
        
        
        '''

        
        
        
        
        
        
        
        
        


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

        for i in range(len(arr)):
            cur_max = 0

            for kk in range(1, k + 1):
                if i - kk + 1 < 0:
                    continue

                cur_max = max(cur_max, arr[i-kk+1])

                # print(i, kk, \",\", i - kk + 1, cur_max, arr[i-kk+1], ':', d[i], d[i-kk])

                d[i] = max(d[i], d[i-kk] + cur_max*kk)

        print(d)

        return d[-2]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0]*(N+1)
        
        for i in range(N):
            curr_max = 0
            for j in range(1, K+1):
                if i+j>N: break
                curr_max = max(curr_max, A[i+j-1])
                dp[i+j] = max(dp[i+j], dp[i]+curr_max*j)
                
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [float('-inf') for i in range(len(A)+1)]
        dp[-1] = 0
        dp[-2] = A[-1]
        
        for j in reversed(list(range(len(A)-1))):
            cur_max = float('-inf')
            for k in range(K):
                if j+k == len(A):
                    break
                cur_max = max(cur_max, A[j+k])
                dp[j] = max(dp[j], (k+1)*cur_max + dp[j+k+1])
        
        return dp[0]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp=[0]*len(arr)
        dp[0]=arr[0]
        for i in range(1, len(arr)):
            maxval=arr[i]
            for j in range(i, i-k, -1):
                if j<0:
                    break
                maxval=max(maxval, arr[j])
                temp=dp[j-1] if j-1>=0 else 0
                temp+=maxval*(i-j+1)
                dp[i]=max(dp[i], temp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], k: int) -> int:
        N = len(A)
        dp = [0] * (N+1)
        
        for i in range(N):
            mx = 0
            #print('i={}'.format(i))
            for j in range(i, max(-1, i-k), -1):
                mx = max(mx, A[j])
                #print('  j={}, mx={}'.format(j, mx))
                p = dp[i+1]
                dp[i+1] = max(dp[i+1], dp[j] + mx * (i-j+1)) 
                #print('  p={}, c={}'.format(p, dp[i+1]))       
            #print('c={}'.format(dp[i+1]))       
        return dp[N]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
            dp = [float('-inf') for i in range(len(A)+1)]
            dp[-1] = 0
            dp[-2] = A[-1]

            for j in reversed(range(len(A)-1)):
                cur_max = float('-inf')
                for k in range(K):
                    if j+k == len(A):
                        break
                    cur_max = max(cur_max, A[j+k])
                    dp[j] = max(dp[j], (k+1)*cur_max + dp[j+k+1])

            return dp[0]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0] * (len(A) + 1)
        
        for i in range(1, len(A) + 1):
            
            tmp = 0
            tmp_max = 0
            
            for j in range(1, min(i,K) + 1):
                tmp_max = max(A[i-j], tmp_max)
                tmp = max(tmp, dp[i-j] + tmp_max * j)
            
            dp[i] = tmp
        
        return dp[len(A)]
        


class Solution:
    def maxSumAfterPartitioning(self, A, K):
        # https://leetcode.com/problems/partition-array-for-maximum-sum/discuss/290863/JavaC%2B%2BPython-DP
        # Use dp (record[i+1]) to record the maximum sum can be obtained from A[0]-A[i]
        # For each position, we loop back 1 to k elements and find the maximum within each range
        # And replace them all with the maximum and try to find the maximum sum based on record[i-k+1]
        n = len(A)
        record = [0]*(n+1)
        for i in range(n):
            curMax = 0
            for k in range(1,min(K,i+1)+1):
                curMax = max(curMax,A[i-k+1])
                record[i+1] = max(record[i+1],record[i-k+1]+curMax*k)
        return record[n]
        
        # N = len(A)
        # dp = [0] * (N + 1)
        # for i in range(N):
        #     curMax = 0
        #     for k in range(1, min(K, i + 1) + 1):
        #         curMax = max(curMax, A[i - k + 1])
        #         dp[i+1] = max(dp[i+1], dp[i+1 - k] + curMax * k)
        # return dp[N]


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0] * (len(A) + 1)
        for i in range(len(A)):
            value = A[i]
            for j in range(1, K + 1):
                if i + j - 1 >= len(A):
                    break
                value = max(A[i + j - 1], value)
                dp[i + j] = max(dp[i] + value * j, dp[i + j])
        return dp[-1]
       
        
            


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):
            m = -float('inf')
            d = 0
            while d < k and i - d > 0:
                m = max(m, arr[i - 1 - d])
                dp[i] = max(dp[i], dp[i - d - 1] + m * (d + 1))
                d += 1
        return dp[n]


'''
So this can be a subproblem of different lengths of k and subarrays

so f([1,15,7,9,2,5,10]) = 1 + f([15,7,9,2,5,10]]) or 15 * 2 + f([7,9,2,5,10]]) or 
                            15 * 3 + f([7,9,2,5,10]])
                            
if not arr, then we return
'''
class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        N = len(arr)

        memo = {}
        def maxSum2(i):
            if i >= N:
                return 0
            if i in memo: return memo[i]
            val = -1
            sol = -1
            # traverse k times or until end of array. + 1 to offset 0 index so we can multiply val * j straight up
            for j in range(1, min(k+1, N - i + 1)):
                val = max(val, arr[i + j -1])
                sol = max(sol, val * j + maxSum2(i + j))
            memo[i] = sol
            return sol
        return maxSum2(0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n + 1)
        for i in range(n):
            currMax = arr[i]
            size = 1
            while size <= k and i - size + 1 >= 0:
                currMax = max(currMax, arr[i - size + 1])
                dp[i + 1] = max(dp[i + 1], dp[i + 1 - size] + (currMax * size))
                size += 1

        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        memo = {}
        def max_sum(idx):
            if idx >= len(arr):
                return 0

            if idx in memo:
                return memo[idx]
            
            subarr_max = float('-inf')
            options = []
            for end in range(idx, min(idx + k, len(arr))):
                subarr_max = max(subarr_max, arr[end])
                subarr_sum = subarr_max * (end - idx + 1)
                options.append(subarr_sum + max_sum(end + 1))
            
            memo[idx] = max(options)
            
            return memo[idx]
            
        return max_sum(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        memo = {}
        def dfs(i):
            if i >= n:
                return 0
            
            if i in memo:
                return memo[i]
            
            res = float('-inf')
            cur_max = float('-inf')
            for j in range(i, min(i + k, n)):
                cur_max = max(cur_max, arr[j])
                res = max(res, cur_max * (j - i + 1) + dfs(j + 1))
            
            memo[i] = res
            return res
        
        return dfs(0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        N = len(arr)
        maxSoFar = [0]*N
        for i in range(N):
            curMax = 0
            for prev in range(1,min(i+1,k)+1):
                curMax = max(curMax,arr[i-prev+1])
                lastPartition = maxSoFar[i-prev] if i >= prev else 0
                maxSoFar[i] = max(maxSoFar[i], lastPartition + curMax*prev)
        return maxSoFar[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        current_max = 0
        dp = [0] * n
        
        for i in range(n):
            if i < k:
                current_max = max(current_max, arr[i])
                dp[i] = (i+1) * current_max
            else:
                current_max = 0
                for j in range(1, k+1):
                    current_max = max(current_max, arr[i - j + 1])
                    dp[i] = max(dp[i], dp[i-j] + current_max * j)
                
        return dp[-1]


class Solution:
    def maxSumAfterPartitioning(self, A, K):
        N = len(A)
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i + 1) + 1):
                curMax = max(curMax, A[i - k + 1])
                dp[i+1] = max(dp[i+1], dp[i+1 - k] + curMax * k)
        print(dp)
        return dp[N]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * n
        for i in range(n):
            currMax = arr[i]
            size = 1
            while size <= k and i - size + 1 >= 0:
                currMax = max(currMax, arr[i - size + 1])
                dp[i] = max(dp[i], (dp[i - size] if i - size >= 0 else 0) + (currMax * size))
                size += 1

        # print(dp)
        return dp[-1]

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

        for i in range(len(arr)):
            cur_max = 0

            for kk in range(1, k + 1):
                if i - kk + 1 < 0:
                    continue

                cur_max = max(cur_max, arr[i-kk+1])

                # print(i, kk, \",\", i - kk + 1, cur_max, arr[i-kk+1], ':', d[i], d[i-kk])
                
                if i - kk < 0:
                    prev = 0
                else:
                    prev = d[i-kk]

                d[i] = max(d[i], prev + cur_max*kk)

        print(d)

        return d[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0 for i in range(len(arr)+1)]
        
        for i in range(len(arr)):
            val = arr[i]
            for j in range(1, k+1):
                if i + j -1 >= len(arr):
                    break
                val = max(arr[i+j-1], val)
                dp[i+j] = max(dp[i] + val *j, dp[i+j])
        return dp[-1]

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

        for i in range(0, len(arr)):
            sub_max = 0
            for j in range(k):
                if j <= i:
                    sub_max = max(sub_max, arr[i-j])
                    dp[i + 1] = max(dp[i+1], sub_max * (j + 1) + dp[i-j])
        
        return dp[len(arr)]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        def dfs(start, memo):
            if start in memo:
                return memo[start]
            N = len(A)
            if start >= N:
                return 0
            maxSum = 0
            maxEle = 0
            for i in range(start, min(N, start + K)):
                maxEle = max(maxEle, A[i])
                maxSum = max(maxSum, maxEle * (i - start + 1) + dfs(i+1, memo))
            memo[start] = maxSum
            return maxSum
        return dfs(0, {})
        
#         max_heap = []
#         counter = collections.defaultdict(int)
#         N = len(A)
#         result = []
#         for i in range(K):
#             heappush(max_heap, -A[i])
#             counter[A[i]] += 1
            
#         for i, n in enumerate(A):
#             if i+k < N:
#                 result.append(-heap[0][0])


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        N = len(arr)
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for j in range(1, min(k, i + 1) + 1):
                curMax = max(curMax, arr[i - j + 1])
                dp[i] = max(dp[i], dp[i - j] + curMax * j)
        return dp[N - 1]

    


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [-1] * (len(arr) + 1)
        dp[0] = 0
        
        for i in range(len(arr)):
            cur_max = -1
            for j in range(k):
                if (i - j) < 0:
                    dp[i + 1] = max(dp[i + 1], arr[i])
                    break
                cur_max = max(cur_max, arr[i-j])
                dp[i + 1] = max(dp[i + 1], dp[i-j] + cur_max * (j + 1))
        
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        if arr == [] or k == 0:
            return 0 
        
        if len(arr) == 1 and k == 1:
            return arr[0] 
        
        l = len(arr)
        res = [0]*(l)

        for i in range(0, l):
            sub_max = 0
            for j in range(k):
                if j <= i:
                    sub_max = max(sub_max, arr[i-j])
                    res[i] = max(res[i], sub_max*(j + 1) + (res[i-j-1] if i-j-1 >=0 else 0))
        
        return res[l-1]

     

        
        

            


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0]*(n+1)
        
        dp[0] = 0
        
        for i in range(1,n+1):
            mx=0
            for j in range(k):
                if(i-j-1>=0):
                    mx = max(mx, arr[i-j-1])
                    dp[i] = max(dp[i], mx*(j+1) + dp[i-j-1])
                
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        dp = len(arr)  * [0]
        dp[0] = arr[0]
        for i in range(1, len(arr)):
            sub_max = 0
            for j in range(k):
                if j <= i:
                    sub_max = max(sub_max, arr[i-j])
                    dp[i] = max(dp[i], sub_max * (j + 1) + (dp[i-j-1] if i-j-1 >= 0 else 0))
        
        return dp[len(arr)-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        # walk through list: at every element, look backwards up to K spaces
        # compare combination of 1, 2 .. K repeats of current segment max
        # vs total sum, and retain the largest (dp_sum memoization)
        # dummy index dp_sum[0] for index bound checking
        # O(AK) time, O(A) extra space

        dp_sum = [0 for _ in range(len(A)+1)]

        for i in range(len(A)):
            seg_max = A[i]

            for j in range(1, K+1):
                if i-j+1 < 0: break

                seg_max = max(seg_max, A[i-j+1])

                tmp = dp_sum[i-j+1] + seg_max * j
                dp_sum[i+1] = max(dp_sum[i+1], tmp)

        return dp_sum[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], k: int) -> int:
        L=len(A)
        vis={}
        def pos(n):
            if n>=L:
                return 0
            if n in vis:
                return vis[n]
            currmax=A[n]
            ans=A[n]+pos(n+1)
            for i in range(1,k):
                n1=n+i
                if n1>=L:
                    break
                currmax=max(currmax,A[n1])
                ans=max(ans,currmax*(i+1)+pos(n1+1))
            vis[n]=ans
            return vis[n]
        return pos(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        if not arr:
            return 0
        n = len(arr)
        dp = [0 for _ in range(n)]
        for i in range(n):
            temp_max = arr[i]
            j = 1
            while i-j+1>=0 and j<=k:
                temp_max = max(temp_max, arr[i-j+1])
                if i>=j:
                    dp[i] = max(dp[i], dp[i-j]+(temp_max*j))
                else:
                    dp[i] = max(dp[i], temp_max*j)
                j+=1
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [-1 for _ in range(n)]
        def max_sum(i):  
            # print(i)
            if i >= n:
                return 0
            if i == (n - 1):
                return arr[i]
            
            if dp[i] != -1:
                return dp[i]
            
            ans = float('-inf')
            maxi = arr[i]
            for p in range(1, k + 1):
                v = maxi*p + max_sum(i + p)
                # print(i, p, v)
                ans = max(v, ans)
                if (i + p) < n:
                    maxi = max(maxi, arr[i + p])
                else:
                    break
            dp[i] = ans
            return ans
        
        v =  max_sum(0)
        return v

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

        for i in range(size):
            maxArr = 0
            for j in range(0, k):
                if i - j >= 0:
                    maxArr = max(maxArr, arr[i - j])
                    candidate = maxArr * (j + 1)
                    candidate += 0 if i - j == 0 else mem[i - j - 1]
                    mem[i] = max(mem[i], candidate)
                else:
                    break
        return mem[size - 1]


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        
        dp = {}
        
        def help(arr,k, start=0):
            
            if start == len(arr):
                return 0
            
            if start in dp:
                return dp[start]
            
            dp[start] = -float('inf')
            maxval = arr[start]
            
            for i in range(start,min(start+k,len(arr))):
                maxval = max(maxval,arr[i])
                dp[start] = max(dp[start],maxval*(i-start+1)+help(arr,k,i+1))
                
            return dp[start]
        
        return help(arr,k)
                
            
                
                


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        N = len(arr)
        K = k
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i + 1) + 1):
                curMax = max(curMax, arr[i - k + 1])
                dp[i] = max(dp[i], dp[i - k] + curMax * k)
        return dp[N - 1]
                


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        # Recursive approach
        memo = {} 
        
        def getMax(arr, k, idx):
            
            # if reached end
            if idx == len(arr): return 0
            if idx in memo: return memo[idx]
            
            maxSum, maxInSub = 0, 0
            for i in range(idx, min(idx+K, len(arr))):
                maxInSub = max(maxInSub, arr[i])
                maxSum = max(maxSum, maxInSub*(i-idx+1) + getMax(arr, k, i+1))
            
            memo[idx] = maxSum
            return maxSum
            
        
        return getMax(A, K, 0)
        
#         # dp[i] will hold the maximum sum 
#         # from [0, i)
#         dp[i] = [0] * (len(A)+1)
        
        
        
        


class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        dp = [0]*len(A)
        dp[0] = A[0]
        partition_max = A[0]
        for x in range(1,K):
            partition_max = max(partition_max, A[x])
            dp[x] = (x+1)*partition_max
        print(dp)
        for i in range(K, len(dp)):
            partition_max = float('-inf')
            for j in range(K):
                partition_max = max(partition_max, A[i-j])
                dp[i] = max(dp[i], dp[i-j-1] + (j+1)*partition_max)
        print(dp)
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:    
        size = len(A)
        if K == 1: return sum(A)
        dp = [0] * (size + 1)
        for i in range(size):
            cur_max = float('-inf')
            block_size = 1
            while block_size <= K and i - block_size + 1 >= 0:
                cur_max = max(cur_max, A[i - block_size + 1])
                #cur_max = max(A[i - block_size + 1:i+1]) if i - block_size + 1 >= 0 else max(A[:i+1])
                dp[i+1] = max(dp[i+1], dp[i - block_size + 1] + block_size * cur_max)
                block_size += 1
        
        return dp[size]



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 j in range(1, min(k, i)+1 ):
                cur_max = max(cur_max, arr[i-j])
                dp[i] = max(dp[i], cur_max*j + dp[i-j])
        return dp[-1]
                
            
        # n = len(arr)
        # memo = {n:0}
        # def helper(arr, i):
        #     if i in memo:
        #         return memo[i]
        #     res = 0
        #     for j in range(i, min(n,i+k)):
        #         res = max(res, helper(arr, j+1)+max(arr[i:j+1])*(j+1-i))
        #     memo[i] = res
        #     return res
        # return helper(arr, 0)


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0]*n
        
        for i in range(n):
            dp[i] = arr[i] + (dp[i-1] if i-1>=0 else 0)
            tmp = arr[i]
            
            for j in range(1,k):
                if i-j>=0:
                    
                    tmp = max(tmp, arr[i-j])
                    
                    dp[i] = max(dp[i], tmp*(i-(i-j)+1)+ (dp[i-j-1] if i-j-1>=0 else 0))
                    
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        dp = [0] * (n+1)
        dp[1] = arr[0]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + arr[i-1]
            cur_max = arr[i-1]
            for j in range(1, k+1): ## j: number of elements in the last group
                cur_max = max(cur_max, arr[i-j])
                if i-j>=0:
                    dp[i] = max(dp[i], dp[i-j]+j*cur_max)
        return dp[n]

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp = [0]*(len(arr)+1)
        
        for i in range(1, len(arr)+1):
            dp[i] = float('-inf')
            curr_max = arr[i-1]
            for p in range(1, k+1):
                if p > i:
                    break
                curr_max = max(curr_max, arr[i-p])
                dp[i] = max(dp[i], p*curr_max + dp[i-p])
        
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        
        self.max_sum = float('-inf')
        self.dic = {}
        
        # @functools.lru_cache(None)
        def getSum(i):
            
            if i>=len(A):
                # if cur_sum>self.max_sum:
                #     self.max_sum = cur_sum
                return 0
            if i in self.dic:
                return self.dic[i]
            cur_max = A[i]
            ret = cur_max + getSum(i+1)
            for j in range(1,K):
                if i+j<len(A):
                    if A[i+j]>cur_max:
                        cur_max = A[i+j]
                    ret = max(cur_max*(j+1) + getSum(i+j+1), ret)
                else:
                    break
            self.dic[i] = ret
            return ret
        
        return getSum(0)

                
                
        
                


class Solution:
    @lru_cache(None)
    def rec(self, idx):
        if idx>len(self.A):
            return 0
        
        max_yet = 0
        max_score = 0
        
        for i in range(self.K):
            if idx+i>=len(self.A):
                break
                
            max_yet = max(max_yet, self.A[idx+i])
            
            max_score = max(max_score, max_yet*(i+1) + self.rec(idx+i+1))
        
        return max_score
        
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        self.A = A
        self.K = K
        
        return self.rec(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        cacheMax=[[0]*len(arr) for i in range(len(arr))]
        for i in range(len(arr)):
            cacheMax[i][i]=arr[i]
        for i in range(1,len(arr)):
            for j in range(max(i-k+1,0),i+1):
                cacheMax[j][i] = max(cacheMax[j][i-1],arr[i])
        
        
        
        
        dp=[0]*(len(arr)+1)
        dp[1]=arr[0]
        for i in range(1,len(arr)):
            for j  in range(max(0,i-k+1),i+1):
                dp[i+1]=max(dp[i+1],dp[j]+cacheMax[j][i]*(i-j+1))
                
            
        return dp[-1]

class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        def DPHelper(index):
            if(index >= len(A)):
                return 0
            
            if(memo.get(index) is not None):
                return memo[index]
            
            res = 0
            curr_max = 0
            
            for i in range(index, min(index + K, len(A))):
                curr_max = max(curr_max, A[i])
                res = max(res, (curr_max * (i - index + 1)) + DPHelper(i + 1))
            
            memo[index] = res
            
            return res
        
        memo = {}
        
        return DPHelper(0)

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp  = [0] * (len(arr) + 1)
        for i in range(1, len(arr) + 1):
            curM = arr[i-1]
            for j in range(1, min(i , k) + 1):
                curM = max(curM, arr[i-j])
                dp[i] = max(dp[i], dp[i-j] + curM * j)
        return dp[-1]
    
    
        # def maxSumAfterPartitioning(self, A, K):
        # N = len(A)
        # dp = [0] * (N + 1)
        # for i in xrange(N):
        #     curMax = 0
        #     for k in xrange(1, min(K, i + 1) + 1):
        #         curMax = max(curMax, A[i - k + 1])
        #         dp[i] = max(dp[i], dp[i - k] + curMax * k)
        # return dp[N - 1]