@@ -0,0 +1,1139 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those%0A * integers. Return the maximum product you can get.%0A * %3Cp%3E%0A * For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).%0A * %3Cp%3E%0A * Note: You may assume that n is not less than 2 and not larger than 58.%0A * %3Cp%3E%0A * Hint:%0A * %3Cp%3E%0A * There is a simple O(n) solution to this problem.%0A * You may check the breaking results of n ranging from 7 to 10 to discover the regularities.%0A * %3Cp%3E%0A * Tags: Dynamic Programming, Math%0A */%0Apublic class IntegerBreak %7B%0A%0A    /**%0A     * Math.%0A     * If factor x %3E= 4, we can decompose it into 2 and (x-2), 2 * (x-2)= 2x - 4 %3E x.%0A     * So the final product will be larger, means that the product won't exceed 4.%0A     */%0A    public int integerBreak(int n) %7B%0A        if (n == 2) %7B%0A            return 1;%0A        %7D%0A        if (n == 3) %7B%0A            return 2;%0A        %7D%0A        int product = 1;%0A        while (n %3E 4) %7B%0A            product *= 3;%0A            n -= 3;%0A        %7D%0A        return product * n;%0A    %7D%0A%7D%0A

add Integer Break