# Java 0ms with explanation

• Assume n = a + b, where a <= b, and an array, table[n+1], which is used to save the intermediate optimum results. Thus, we can always break n into only two positive integers. For example, when going to n = 5 = 2+3 = 2+2+1, we do not need to consider 2+2+1 as table[3] already saved the optimum result.

After some runs, you will notice the magic number 3!

``````n                  table[n]      optimization
-------------------------------------------------
2     1+1       1
3     1+2       2
4     1+3
2+2       4                4 * 3^0
5     1+4
2+3       6                2 * 3^1
6     1+5
2+4
3+3       9                3 * 3^1
7     1+6
2+5
3+4       12              4 * 3^1
8     1+7
2+6
3+5       18              2 * 3^2
4+4
9     1+8
2+7
3+6       27              3 * 3^2
4+5
...
``````

You will find when a=3, it always give the max value. I didn't find a proper way to explain it but you will notice when a>3, although the left part containing a will increase, the right part containing b will decrease to the same extent or even more. That is, for a=3, table[a+i]/table[a] <= table[b]/table[b-i], where i = 1,2,3...

Then you can optimize it by finding the pattern shown above and here is the code.

``````public class Solution {
public int integerBreak(int n) {
if(n<4) return n-1;
int index = (n-2)/3;
return (n-3*index) * (int)Math.pow(3, index);
}
}
``````

Any comments and suggestions are welcomed.

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