@@ -0,0 +1,909 @@
+// Solution runs in O(n%5E2) time and uses O(n) space%0A// Beats 47.67%25 of submissions%0Aclass Solution %7B%0A  public int integerBreak(int n) %7B%0A    int max = 0;%0A    int%5B%5D memo = new int%5Bn+1%5D;%0A    for (int i = 1; i %3C n; i++) %7B%0A      max = Math.max(max, helper(n - i, memo) * i);%0A    %7D%0A    return max;%0A  %7D%0A%0A  private int helper(int n, int%5B%5D memo) %7B%0A    if (n %3C= 1) return 1;%0A    if (memo%5Bn%5D %3E 0) return memo%5Bn%5D;%0A    int product = 1;%0A    for (int i = 1; i %3C= n; i++) %7B%0A      product = Math.max(product, helper(n - i, memo) * i);%0A    %7D%0A    memo%5Bn%5D = product;%0A    return product;%0A  %7D%0A%7D%0A%0A// DP solution O(n%5E2) time and O(n) space%0Aclass Solution %7B%0A  public int integerBreak(int n) %7B%0A    int%5B%5D dp = new int%5Bn+2%5D;%0A    dp%5B0%5D = 1; dp%5B1%5D = 1;%0A    for (int i = 2; i %3C= n; i++) %7B%0A      for (int j = 1; j %3C i; j++) %7B%0A        dp%5Bi%5D = Math.max(dp%5Bi%5D, Math.max(dp%5Bj%5D, j) * Math.max(dp%5Bi-j%5D, i-j));%0A      %7D%0A    %7D%0A    return dp%5Bn%5D;%0A  %7D%0A%7D%0A

add solution