package leetcode;

/**
 * https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/
 */
public class Problem1423 {
    public int maxScore(int[] cardPoints, int k) {
        return maxScore(cardPoints, k, 0, cardPoints.length - 1,
            new Integer[cardPoints.length][cardPoints.length]);
    }

    private static int maxScore(int[] cardPoints, int k, int i, int j, Integer[][] memo) {
        if (k == 0) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int a = maxScore(cardPoints, k - 1, i + 1, j, memo) + cardPoints[i];
        int b = maxScore(cardPoints, k - 1, i, j - 1, memo) + cardPoints[j];
        int max = Math.max(a, b);
        memo[i][j] = max;
        return max;
    }

    public static void main(String[] args) {
        Problem1423 prob = new Problem1423();
        System.out.println(prob.maxScore(new int[]{1,2,3,4,5,6,1}, 3)); // 12
        System.out.println(prob.maxScore(new int[]{2,2,2}, 2)); // 4
        System.out.println(prob.maxScore(new int[]{9,7,7,9,7,7,9}, 7)); // 55
        System.out.println(prob.maxScore(new int[]{1,1000,1}, 1)); // 1
        System.out.println(prob.maxScore(new int[]{1,79,80,1,1,1,200,1}, 3)); // 202
        System.out.println(prob.maxScore(new int[]{1,79,80,1,1,1,200,1}, 4)); // 281
    }
}

@@ -185,107 +185,33 @@
     
-return maxScore(cardPoints, k, 0, cardPoints.length - 1,%0A            new Integer%5BcardPoints.length%5D
+int%5B%5D prefixSum = new int
 %5Bcar
@@ -229,109 +229,68 @@
 gth%5D
-)
 ;%0A    
-%7D%0A%0A
     
-private static int maxScore(int%5B%5D cardPoints, int k, int i, int j, Integer%5B%5D%5B%5D memo) %7B%0A
+for (int i = 0; i %3C cardPoints.length; i++) %7B%0A    
     
@@ -297,17 +297,17 @@
     if (
-k
+i
  == 0) %7B
@@ -323,16 +323,40 @@
     
+    p
 re
-turn 0
+fixSum%5Bi%5D = cardPoints%5Bi%5D
 ;%0A  
@@ -365,44 +365,25 @@
     
-%7D%0A
     
-    if (memo%5Bi%5D%5Bj%5D != null) %7B%0A
+%7D else %7B%0A    
     
@@ -394,199 +394,197 @@
     
+p
 re
-turn memo%5Bi%5D%5Bj%5D;%0A        %7D%0A        int a = maxScore(cardPoints,
+fixSum%5Bi%5D = prefixSum%5Bi - 1%5D + cardPoints%5Bi%5D;%0A            %7D%0A        %7D%0A        int answer = 0;%0A        for (int i =
  k - 1
-, i + 1, j, memo) + cardPoints%5Bi%5D;%0A        int b = maxScore(cardPoints, k - 1, i, j - 1, memo) + cardPoints%5Bj%5D;%0A
+; i %3E= 0; i--) %7B%0A            if (i - k + 1 == 0) %7B%0A       
         
 int 
@@ -579,23 +579,23 @@
         
-int max
+ answer
  = Math.
@@ -603,624 +603,466 @@
 ax(a
-, b);%0A        memo%5Bi%5D%5Bj%5D = max;%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1423 prob = new Problem1423();%0A        System.out.println(prob.maxScore(new int%5B%5D%7B1,2,3,4,5,6,1%7D, 3)); // 12%0A        System.out.println(prob.maxScore(new int%5B%5D%7B2,2,2%7D, 2)); // 4%0A        System.out.println(prob.maxScore(new int%5B%5D%7B9,7,7,9,7,7,9%7D, 7)); // 55
+nswer, prefixSum%5Bi%5D);%0A            %7D else %7B%0A                int sum = prefixSum%5Bi%5D + getSuffixSum(prefixSum, cardPoints.length + i - k + 1);%0A                answer = Math.max(answer, sum);%0A            %7D%0A        %7D%0A        return Math.max(answer, getSuffixSum(prefixSum, cardPoints.length - k));
 %0A    
+%7D%0A%0A
     
-System.out.println(prob.maxScore(new int%5B%5D%7B1,1000,1%7D, 1)); // 1%0A        System.out.println(prob.maxScore(new int%5B%5D%7B1,79,80,1,1,1,200,1%7D, 3)); // 202%0A        System.out.println(prob.maxScore(new int%5B%5D%7B1,79,80,1,1,1,200,1%7D, 4)); // 281
+private static int getSuffixSum(int%5B%5D prefixSum, int index) %7B%0A        return prefixSum%5BprefixSum.length - 1%5D - (index - 1 %3C 0 ? 0 : prefixSum%5Bindex - 1%5D);
 %0A   

Solve problem 1423