The idea is to maximize:

- f(n) = f(i)*f(n-i)
- It is intuitive to use DP then

It is easier for me to come up with this DP solution. The highest-voted solution is considering math, about factoring 2 or 3, while it is not easy for me to make such a thought.

Attached is my 1ms AC code:

```
public class Solution {
int[] dict;
public int integerBreak(int n) {
dict = new int[n+1];
//Handle n=2 and n=3
if(n<=3) return n-1;
return helper(n);
}
private int helper(int n){
if(n<=4) return n;
if(dict[n]!=0) return dict[n];
int res = 0;
for(int i=2;i<=n/2;i++){
int tmp1=helper(i), tmp2 = helper(n-i);
int tmp = tmp1*tmp2;
if(res<tmp)
res = tmp;
}
dict[n]=res;
return dict[n];
}
}
```