C++ O(n) solution


  • 0

    This is written in a more generalized way.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.