class Solution {public: int integerBreak(int n) { vector<int> dp(n+1, 1); for(int i = 3; i<= n;i++){ for(int j = 1; j< i;j++){ dp[i] = max(max(dp[i], dp[i - j] * j % 1000000007), (i - j) * j % 1000000007); } } return dp[n] % 1000000007; }};