Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 500
	0 &lt;= arr[i] &lt;= 109
	1 &lt;= k &lt;= arr.length


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

        def dfs(start):
            if start == N: # base case, so in tabulation we go [N - 1]...[0], as [N] = 0
                return 0
            
            maxi = float(-inf)
			# you partition at every position up to start + k and repeat the same process for the next partition
			# e.g. 1 9 3, k = 2
			# 1|9|3 => with max in each partition: 1|9|3 = 13
			# 1|9 3 => with max in each partition: 1|9 9 = 19
			# 1 9|3 => with max in each partition: 9 9|3 = 21
			# get max_in_partition(start,end) + give_me_max_for_array(previous_partition_end + 1, N)
			# rec.relation = max(max_sum_in_partition[start, end] + dfs(end + 1)))
            for end in range(start, min(N, start + k)):
                maxi = max(maxi, get_max(start, end) + dfs(end + 1))
            return maxi
        
        N = len(nums)
        return dfs(0)
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
         return maxSum(arr,k, 0 );

    }
    public int maxSum(int[] arr, int k, int start) {
        int curr1 = 0, curr2= 0;
        int prev = 0;
        int max = 0;

        Map<String, Integer> memo = new HashMap();
        //memo.put("0,0", arr[0]);

        for(int i=0; i< arr.length; ++i){
            //without current element
            curr1 = prev + arr[i];

            //with current element, find max if p=0...k (since subarray can be longeth of at most k)
            int tempk = 0, half1 = 0, half2 = 0, temp= 0;
            for(int p=0; p<=k; ++p){
                half1 = findMaxSumWithKEle(arr, p , i);
                tempk = i-p;
                half2 = memo.get(("0,"+tempk)) == null ? 0: memo.get(("0,"+tempk));
                if(temp < half1 + half2){
                    temp = half1 + half2;
                }
            }

            curr2 = temp;

            //find max between curr1 or curr2 - with current elemtn in the subarray or outside the subarray
            max = (curr1 < curr2) ? curr2:curr1;

            //add in memo
            String key= "0," + i;
            memo.put(key, max);
            System.out.println("Max: " + max + " from [" + key + "]");
            prev = max;
        }

        return max;
    }

    public static Integer findMaxSumWithKEle(int[] arr, int k, int end) {
        int max= 0;
        if(end > arr.length || end<0){
            return 0;
        }
        int c = 0;
        for(int i=end; i> (end -k ) && i>=0; --i){
            ++c;
            if(max < arr[i]){
                max = arr[i];
            }
        }
        return max *c;
    }
}
class Solution {
public:

    int get_max(vector<int>&arr , int s , int e ){
        int mx_val = *max_element(arr.begin() + s , arr.begin() + e + 1);
        return (e-s + 1 )* mx_val ;
    }

    int solve( vector<int>&arr , int idx , int k , vector<vector<int>>&dp){

        if(idx >= arr.size() ) return 0;

        if(dp[idx][k] != -1 )
            return dp[idx][k];

        int ans = 0;

        for(int i = 0 ; i<k ; ++i ){
            if((idx + i ) > arr.size() - 1)
                break;

            int val = get_max(arr , idx , idx + i ) + solve( arr , idx + i + 1 , k , dp );
            ans = max( ans , val );
        }
        return dp[idx][k] = ans ;

    }

    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        vector<vector<int>>dp(arr.size()+1 , vector<int>( k + 1 , -1 ));

        return solve( arr , 0 , k , dp );
    }
};
/** https://leetcode.com/problems/partition-array-for-maximum-sum/
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maxSumAfterPartitioning = function(arr, k) {
  // Array to hold max value for each integer in `arr`
  let dp = Array(arr.length).fill(0);
  dp[0] = arr[0];
  
  // Calculate max value for each integer
  for (let i = 1; i < arr.length; i++) {
    // The `maxK` is largest number from `i` to `i - k - 1`
    let maxK = 0;
    
    // The `maxVal` is for holding max value to be added to `dp[i]`
    let maxVal = 0;
    
    // Loop through `i` to `i - k - 1`
    for (let j = 1; j <= k; j++) {
      // Get max number
      maxK = Math.max(maxK, arr[i - (j - 1)]);
      
      // Calculate `maxVal`, if current `i` is smaller than `k`, we don't need to continue
      if (i < j) {
        maxVal = Math.max(maxVal, maxK * j);
        break;
      }
      
      maxVal = Math.max(maxVal, dp[i - j] + (maxK * j));
    }
    
    // Store `maxVal`
    dp[i] = maxVal;
  }
  
  return dp[dp.length - 1];
};
Partition Array for Maximum Sum