package leetcode;

/**
 * https://leetcode.com/problems/partition-array-for-maximum-sum/
 */
public class Problem1043 {
    public int maxSumAfterPartitioning(int[] A, int K) {
        return maxSumAfterPartitioning(A, K, 0, new Integer[A.length]);
    }

    private static int maxSumAfterPartitioning(int[] array, int k, int index, Integer[] memo) {
        if (index >= array.length) {
            return 0;
        }
        if (memo[index] != null) {
            return memo[index];
        }
        int answer = array[index];
        int[] max = new int[k];
        for (int i = 0, j = index; j < index + k && j < array.length; i++, j++) {
            if (i == 0) {
                max[i] = array[j];
            } else {
                max[i] = Math.max(max[i - 1], array[j]);
            }
        }
        for (int i = 0; i < k; i++) {
            if (index + i >= array.length) {
                break;
            }
            int val = maxSumAfterPartitioning(array, k, index + i + 1, memo) + (max[i] * (i + 1));
            answer = Math.max(answer, val);
        }
        memo[index] = answer;
        return answer;
    }
}

@@ -541,27 +541,16 @@
  int
-%5B%5D
  max = 
-new int%5Bk%5D
+0
 ;%0A  
@@ -573,90 +573,65 @@
  = 0
-, j = index; j %3C index + k && j %3C array.length; i++, j++) %7B%0A            if (i == 0
+; i %3C k; i++) %7B%0A            if (index + i %3E= array.length
 ) %7B%0A
@@ -650,25 +650,13 @@
     
-max%5Bi%5D = array%5Bj%5D
+break
 ;%0A  
@@ -670,15 +670,8 @@
    %7D
- else %7B
 %0A   
@@ -683,18 +683,11 @@
     
-    max%5Bi%5D
+max
  = M
@@ -701,23 +701,16 @@
 (max
-%5Bi - 1%5D
 , array%5B
 j%5D);
@@ -709,156 +709,20 @@
 ray%5B
-j%5D);%0A            %7D%0A        %7D%0A        for (int i = 0; i %3C k; i++) %7B%0A            if (index + i %3E= array.length) %7B%0A                break;%0A            %7D
+index + i%5D);
 %0A   
@@ -805,11 +805,8 @@
 (max
-%5Bi%5D
  * (

Update problem 1043