Let me illustrate the regularity

n=1: return 1

n=2: return 1 (1+1)

n=3: return 2 (1+2)

n=4: return 4 (2+2)

n=5: return 5 (2+3)

Actually when n is bigger than 5, there is a regularity

n=6: return 9 (3+3)

n=7: return 12 (3+2+2)

n=8: return 18 (3+3+2)

n=9: return 27 (3+3+3)

n=10: return 36 (3+3+2+2)

n=11: return 54 (3+3+3+2)

n=12: return 81 (3+3+3+3)

we can see that if the remainder when n is divided by 3 is 0, the maximum product is consists of no two and all three; if the remainder is 1, the maximum product is consists of 2 two and the others are three; if the remainder is 2, the maximum product is consists of 1 two and the others are three.

```
class Solution {
public:
int integerBreak(int n) {
if(n==1) return 1;
if(n<=3) return n-1;
if(n==4) return 4;
if(n==5) return 6;
int n_2 = n%3;
if(n_2==0) return pow(3,n/3);
if(n_2==1) return pow(3,(n-4)/3)*4;
else return pow(3,(n-2)/3)*2;
}
};
···
```