package leetcode;

/**
 * https://leetcode.com/problems/integer-break/
 */
public class Problem343 {
    public int integerBreak(int n) {
        Integer[] memo = new Integer[n + 1];
        return integerBreak(n, memo);
    }

    private static int integerBreak(int n, Integer[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (memo[n] != null) {
            return memo[n];
        }
        int max = 0;
        for (int i = 1; i < n; i++) {
            int x1 = n - i;
            int y1 = n - x1;
            int x2 = integerBreak(x1, memo);
            int x = Math.max(x1, x2);
            int y2 = integerBreak(y1, memo);
            int y = Math.max(y1, y2);
            max = Math.max(x * y, max);
        }
        memo[n] = max;
        return max;
    }
}

@@ -127,24 +127,562 @@
 ak(int n) %7B%0A
+        int%5B%5D memo = new int%5Bn + 1%5D;%0A        int max = 0;%0A        for (int i = 2; i %3C= n; i++) %7B%0A            int tmpMax = 0;%0A            for (int j = 1; j %3C i; j++) %7B%0A                int x1 = i - j;%0A                int y1 = i - x1;%0A                int x = Math.max(x1, memo%5Bx1%5D);%0A                int y = Math.max(y1, memo%5By1%5D);%0A                tmpMax = Math.max(x * y, tmpMax);%0A            %7D%0A            max = Math.max(max, tmpMax);%0A            memo%5Bi%5D = max;%0A        %7D%0A        return max;%0A    %7D%0A%0A//    public int integerBreak(int n) %7B%0A//
         Inte
@@ -706,32 +706,34 @@
 Integer%5Bn + 1%5D;%0A
+//
         return i
@@ -754,23 +754,29 @@
  memo);%0A
+//
     %7D%0A
-%0A
+//%0A//
     priv
@@ -824,24 +824,26 @@
 r%5B%5D memo) %7B%0A
+//
         if (
@@ -848,24 +848,26 @@
  (n == 0) %7B%0A
+//
             
@@ -872,24 +872,26 @@
   return 0;%0A
+//
         %7D%0A  
@@ -880,32 +880,34 @@
  0;%0A//        %7D%0A
+//
         if (n ==
@@ -908,24 +908,26 @@
  (n == 1) %7B%0A
+//
             
@@ -936,16 +936,18 @@
 turn 1;%0A
+//
         
@@ -940,32 +940,34 @@
  1;%0A//        %7D%0A
+//
         if (memo
@@ -977,24 +977,26 @@
  != null) %7B%0A
+//
             
@@ -1011,16 +1011,18 @@
 emo%5Bn%5D;%0A
+//
         
@@ -1015,32 +1015,34 @@
 n%5D;%0A//        %7D%0A
+//
         int max 
@@ -1038,32 +1038,34 @@
    int max = 0;%0A
+//
         for (int
@@ -1078,32 +1078,34 @@
 ; i %3C n; i++) %7B%0A
+//
             int 
@@ -1116,16 +1116,18 @@
  n - i;%0A
+//
         
@@ -1143,24 +1143,26 @@
 1 = n - x1;%0A
+//
             
@@ -1186,32 +1186,34 @@
 reak(x1, memo);%0A
+//
             int 
@@ -1230,24 +1230,26 @@
 ax(x1, x2);%0A
+//
             
@@ -1281,16 +1281,18 @@
  memo);%0A
+//
         
@@ -1321,16 +1321,18 @@
 1, y2);%0A
+//
         
@@ -1359,24 +1359,26 @@
  * y, max);%0A
+//
         %7D%0A  
@@ -1367,32 +1367,34 @@
 x);%0A//        %7D%0A
+//
         memo%5Bn%5D 
@@ -1392,32 +1392,34 @@
  memo%5Bn%5D = max;%0A
+//
         return m
@@ -1418,20 +1418,22 @@
 return max;%0A
+//
     %7D%0A%7D%0A

Update problem 343