0ms C++ solution, using arithmetic-geometric means inequality.


  • 0
    V

    Using arithmetic-geometric means inequality we know that, the product of i elements with given total sum is maximal, when those elements are equal. So, we can just try divide our number into 2,3,...,n elements, and return maximal result. We must remember that given ,,i" doesn't have to divide n, so we must consider n%i elements equal n/i+1 and i-n%i element equal n/i:

    int integerBreak(int n) {
            int res = 0;
            for (int i = 2; i <= n; ++i)
                res = max(res, (int)pow(n/i+1, n%i)*(int)pow(n/i, i-n%i));
            return res;
        }
    

  • 0
    N

    According to my observation, sum will increase and reaches a peek, and then decrease, and keep decreasing, so the count of loops can hold a half of your code.


Log in to reply
 

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