LeetCode [343] Integer Break

 343. Integer Break

Medium

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

1 2 3 4 5 6 7 8 9 10 11 12 13

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