<p>Given an integer <code>n</code>, break it into the sum of <code>k</code> <strong>positive integers</strong>, where <code>k &gt;= 2</code>, and maximize the product of those integers.</p>

<p>Return <em>the maximum product you can get</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> 2 = 1 + 1, 1 &times; 1 = 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 36
<strong>Explanation:</strong> 10 = 3 + 3 + 4, 3 &times; 3 &times; 4 = 36.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 58</code></li>
</ul>

class Solution {
public:
    int integerBreak(int n) {
            // If an optimal product contains a factor f >= 4, then we can replace it
                // with 2 and f - 2 without losing optimality. As 2(f - 2) = 2f - 4 >= f,
                    // we never need a factor >= 4, meaning we only need factors 1, 2, and 3
                        // (and 1 is wasteful).
                            // Also, 3 * 3 is better than 2 * 2 * 2, so we never use 2 more than twice.
                                if (n == 2)  // 1 * 1
                                      return 1;
                                          if (n == 3)  // 1 * 2
                                                return 2;

                                                    int ans = 1;

                                                        while (n > 4) {
                                                              n -= 3;
                                                                    ans *= 3;
                                                                        }
                                                                            ans *= n;

                                                                                return ans;
    }
};
7200