Based on the hint, I think we'd better divide n to 3's + 2's to get maximum. So we can do it in O(1) time. The following is my accepted answer.

```
class Solution {
public:
int integerBreak(int n) {
if (n <= 3) return n-1;
int ret = 1;
int mod = n%3;
if ( mod == 1)
{
n -= 4;
ret = 4;
}
ret *= pow(3, n/3) * (mod ? mod : 1);
return ret;
}
};
```