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; } }