Q54 Partition Array for Maximum Sum - LeetCode1043

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
     /* front partitioning , we partition the left as we go for atmost length k and make 
     a right call to (i+1)to give its best sum of partition of k <=3
     */   
        int n = arr.length;
        // return solve(arr , 0 ,k , new Integer[n] );

        int dp[] = new int[n+1];
        for(int i = n-1 ; i>=0 ; i--){
            int max = (int)-1e9;
            int maxe = Integer.MIN_VALUE;   //max element
            int len = 0 ;
            for(int j = i ; j < Math.min(n , i+k) ; j++){
                len++;
                maxe = Math.max(maxe , arr[j]);
                int sum = len*maxe + dp[j+1];

                max = Math.max(sum ,max);
            }

            dp[i] = max;
        }

        return dp[0];
        
    }

    //REcursion k^n memo n*k | sc- n(dp array) + n(stack height)
    public int solve(int[] arr , int i , int k ,Integer[] dp){
        int n = arr.length;
        if(i == n) return 0;

        if(dp[i] != null)
        return dp[i];

        int max = (int)-1e9;
        int maxe = Integer.MIN_VALUE;   //max element
        int len = 0 ;
        for(int j = i ; j < Math.min(n , i+k) ; j++){
            len++;
            maxe = Math.max(maxe , arr[j]);
            int sum = len*maxe + solve(arr , j+1 ,k , dp);

            max = Math.max(sum ,max);
        }

        return  dp[i] = max;
    }
}