package leetcode;

/**
 * https://leetcode.com/problems/integer-break/
 */
public class Problem343 {
    public int integerBreak(int n) {
        if (n == 1) {
            return 1;
        }
        int x = n / 2;
        int y = n - x;
        int n1 = integerBreak(x);
        int n2 = integerBreak(y);
        int multiply1 = x * y;
        int multiple2 = n1 * n2;
        int max = Math.max(multiply1, multiple2);
        return max;
    }

    public static void main(String[] args) {
        Problem343 prob = new Problem343();
        System.out.println(prob.integerBreak(2)); // 1
        System.out.println(prob.integerBreak(10)); // 36
        System.out.println(prob.integerBreak(1)); // 1
        System.out.println(prob.integerBreak(14)); // 162
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -176,24 +176,189 @@
 ak(int n) %7B%0A
+        Map%3CInteger, Integer%3E memo = new HashMap%3C%3E();%0A        return integerBreak(n, memo);%0A    %7D%0A%0A    private int integerBreak(int n, Map%3CInteger, Integer%3E memo) %7B%0A
         if (
@@ -362,17 +362,17 @@
 f (n == 
-1
+0
 ) %7B%0A    
@@ -386,17 +386,17 @@
  return 
-1
+0
 ;%0A      
@@ -412,185 +412,199 @@
    i
-nt x = n / 2;%0A        int y = n - x;%0A        int n1 = integerBreak(x);%0A        int n2 = integerBreak(y);%0A        int multiply1 = x * y;%0A        int multiple2 = n1 * n2;%0A
+f (n == 1) %7B%0A            return 1;%0A        %7D%0A        if (memo.containsKey(n)) %7B%0A            return memo.get(n);%0A        %7D%0A        int max = 0;%0A        for (int i = 1; i %3C n; i++) %7B%0A  
         
 int 
@@ -603,390 +603,316 @@
     
+  
 int 
-max = Math.max(multiply1, multiple2);%0A        return max
+x1 = n - i;%0A            int y1 = n - x1
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem343 prob = new Problem343();%0A        System.out.println(prob.integerBreak(2)); // 1%0A        System.out.println(prob.integerBreak(10)); // 36%0A        System.out.println(prob.integerBreak(1)); // 1%0A        System.out.println(prob.integerBreak(14)); // 162
+    int x2 = integerBreak(x1, memo);%0A            int x = Math.max(x1, x2);%0A            int y2 = integerBreak(y1, memo);%0A            int y = Math.max(y1, y2);%0A            max = Math.max(x * y, max);%0A        %7D%0A        memo.put(n, max);%0A        return max;
 %0A   

Solve problem 343