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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

Hint:

1. There is a simple O(n) solution to this problem.
2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities

设想对于每个n，有n = i + S, 也就是S = n - i，S可以代表一个数或者一个以上的数的和。（也就是说n是任意两个数之和，或者两个以上的数之和）。令f(n)代表n所对应的最大乘积。

对于第一种情况，f(n) = i * (n - i);

对于第二种情况，i是至少三个数的和，也就是说S = n - i至少是两个数的和，所以S对应的最大乘积为f(n - i),则f(n) = f(n - i) * i;

也就是说 f(n) = max(i*(n-i),f(n-i)*i);

代码如下：

class Solution {public:    int integerBreak(int n) { if (n <= 2) return 1; vector
    
      maxArr(n+1, 0); maxArr[1] = 0; maxArr[2] = 1; // 2=1+1 so maxArr[2] = 1*1 for (int i=3; i<=n; i++) { for (int j=1; j