# Java DP solution

• public class Solution {
public static int[] memo;
public int integerBreak(int n) {
if(memo == null){
memo = new int[n + 10];
memo[0] = 0;
memo[1] = 1;
}
if(memo.length < n + 1){
int[] temp = new int[(2*n) + 1];
for(int j = 0; j < memo.length; j++){
temp[j] = memo[j];
}
memo = temp;
}

if(memo[n] != 0){
return memo[n];
}

for(int k = 2; k <= n; k++){
if(memo[k] == 0){
int max = 0;
for(int i = 1; i < k; i++){
int temp = (k - i) > memo[k - i] ?
(k - i) * i : memo[k - i] * i;
max = max > temp ? max : temp;
}
memo[k] = max;
}
}

return memo[n];
}
}

This solution uses memoization and amortized doubling on the memoized array. Something that gave me trouble was the fact that some n's have a solution which is smaller than n, which throws off larger solutions. That is the reason for checking if k - i > memo[k - i], otherwise i would be including 1's in the solution when there shouldn't be any.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.