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

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

    public static void main(String[] args) {
        Problem1043 prob = new Problem1043();
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{1, 2, 3, 4}, 1)); // 10
        System.out.println(prob.maxSumAfterPartitioning(new int[]{1, 2, 3, 4}, 3)); // 13
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{1, 15, 7, 9, 2, 5, 10}, 3)); // 84
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{1, 15, 7, 10, 2, 5, 9}, 3)); // 84
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{1, 15, 7, 10, 2, 5, 9}, 4)); // 87
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{10, 15, 7, 9, 2, 5, 1}, 4)); // 81
//        System.out.println(prob.maxSumAfterPartitioning(new int[]{10, 15, 7, 9, 2, 5, 1}, 2)); // 68
    }
}

@@ -216,16 +216,39 @@
 (A, K, 0
+, new Integer%5BA.length%5D
 );%0A    %7D
@@ -325,16 +325,32 @@
 nt index
+, Integer%5B%5D memo
 ) %7B%0A    
@@ -406,32 +406,109 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bindex%5D != null) %7B%0A            return memo%5Bindex%5D;%0A        %7D%0A
         int answ
@@ -538,37 +538,31 @@
     
-for (int i = 1; i %3C k; i++) %7B
+int%5B%5D max = new int%5Bk%5D;
 %0A   
@@ -570,53 +570,55 @@
     
-    
+for (
 int 
-val
+i
  = 0
-;%0A            if (index + i %3E=
+, j = index; j %3C index + k && j %3C
  arr
@@ -618,32 +618,42 @@
 j %3C array.length
+; i++, j++
 ) %7B%0A            
@@ -656,18 +656,21 @@
     
-    break;
+if (i == 0) %7B
 %0A   
@@ -679,89 +679,52 @@
     
-   %7D%0A
        
-     int max = 0;%0A            for (int j = index; j %3C index + i; j++)
+max%5Bi%5D = array%5Bj%5D;%0A            %7D else
  %7B%0A 
@@ -741,16 +741,19 @@
      max
+%5Bi%5D
  = Math.
@@ -759,16 +759,23 @@
 .max(max
+%5Bi - 1%5D
 , array%5B
@@ -805,125 +805,92 @@
     
-    val = maxSumAfterPartitioning(array, k, index + i) + (max * (i + 1));%0A            answer = Math.max(answer, val);
+%7D%0A        for (int i = 0; i %3C k; i++) %7B%0A            if (index + i %3E= array.length) %7B
 %0A   
@@ -894,26 +894,24 @@
         
-%7D%0A
         
 return a
@@ -906,817 +906,234 @@
     
+b
 re
-turn answer
+ak
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem1043 prob = new Problem1043();%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B1, 2, 3, 4%7D, 1)); // 10%0A        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B1, 2, 3, 4%7D, 3)); // 13%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B1, 15, 7, 9, 2, 5, 10%7D, 3)); // 84%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B1, 15, 7, 10, 2, 5, 9%7D, 3)); // 84%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B1, 15, 7, 10, 2, 5, 9%7D, 4)); // 87%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B10, 15, 7, 9, 2, 5, 1%7D, 4)); // 81%0A//        System.out.println(prob.maxSumAfterPartitioning(new int%5B%5D%7B10, 15, 7, 9, 2, 5, 1%7D, 2)); // 68
+    %7D%0A            int val = maxSumAfterPartitioning(array, k, index + i + 1, memo) + (max%5Bi%5D * (i + 1));%0A            answer = Math.max(answer, val);%0A        %7D%0A        memo%5Bindex%5D = answer;%0A        return answer;
 %0A   

Solve problem 1043