<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:
    void searchAndFind(vector<int>&dp,int right){
        int l = 1;
        int target = right;
        int r = right -1;
        while(l <= r){
            int total = l + r;
            if(total == target){
                dp[target] = max({dp[l]*r, dp[r]*l, dp[target], dp[l]*dp[r], l*r});
                l++;
                r--;
            }
            else if(total < target){
                l++;
            }else{
                r--;
            }
        }
        return;
    }
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        dp[2] = 1;
        dp[1] = 1;
        for(int i = 2; i<= n; i++){
            searchAndFind(dp, i);
        }
        for(int i = 0; i<= n; i++){
            cout<< dp[i]<< " ";
        }
        return dp[n];
    }

};
7900