It is well-known that the algorithm should return the result by breaking n into factors 2 or 3, and also many other authors have been revealed the reasons for that. However, there are still some ambiguous questions about their explanations. For example, why does n have to break down as n=x+x+...+x ?, and why choosing 3 as factors is better than 2?

Hence, here I want to share a more strict proof of the correctness of the algorithm.

/**

* Given n, let m be the number of summands so that a1+a2+...+am =

* n. By the Inequality of Arithmetic and Geometric Means, we have:

*

* a1 * a2 * ... * am <= (n/m)^m (i.e., power(n/m, m)) and that

* equality holds iff (if and only if) a1=a2=...=am.

*

* Now let x=n/m, and consider the function f(x)=x^(n/x), we are

* going to find its max. Let y=ln[f(x)]=(n/x) * ln(x). Then:

*

* y' = -(n/x^2) * ln(x) + (n/x) * (1/x) = (n/x^2) * [ln(e)-ln(x)],

*

* where e=exp(1)=2.71828... . Since ln() is an increasing function,

* so

*

* f(x) is increasing iff y is increasing iff y'>0 iff

* [ln(e)-ln(x)]>0 iff x<e; and is decreasing iff x>e; and is

* maximized when x=e.

*

* Since x is an integer, x=2 or 3 would maximize f(x). Now let's

* check which of f(2), f(3) is bigger.

*

* Since ln[f(x)]=n * ln(x)/x, and ln(2)/2 < ln(3)/3, so f(3) is the

* max.

*

* In order words, f(x) is maximized at 3 among all !integer! x.

* Given the fact that n, m, x are all integers, and the equality

* condition of the Inequality of Arithmetic and Geometric Mean, we

* have the following two results:

*

* 1. Notice that every non-negative integer n can be broken down as

* n = r * 3 + s * 2, for some non-negatives r,s. (This can be proved by

* induction or by the fact that the greatest common divisor of 3

* and 2 is 1.) Thus, x = 2 or 3 is always attainable. Therefore,

* the product P = a1 * a2 * ... * am is maximized only when ai = 2

* or 3, for all i.

*

* 2. If x=3 is attainable, i.e., if n/m=3, i.e., if n%3==0, then

* the product P is maximized when ai = 3, for all i.

*

* Now the only uncertain is the cases n=3k+1 or 3k+2, for some

* positive integer k. Why do they have to break down as 3(k-1)+2 * 2

* and 3k+2 to achieve the max of the product P?

*

* From 1, we have P must be maximized when n is broken down as

* n = r * 3 + s * 2, for some non-negatives r,s. Hence s=(n-3r)/2, so

*

* P(r) = (3^r)(2^s) = (3^r)(2^((n-3r)/2)), and ln(P) =

* rln(3)+[(n-3r)ln(2)]/2.

*

* Let z=ln(P), then z'=ln(3)-3ln(2)/2 > 0. Hence, P(r) is an

* increasing function. And so P is always maximized when r is the

* largest !attainable! non-negative integer. Strictly saying, P is

* maximized when r is the largest non-negative integer, so that

* n = r * 3 + s * 2 with s being also a non-negative integer.

*

* Until now, we are all clear about the reasons why we break down

* the integer n as what it should be for all cases of n=3k, 3k+1

* and 3k+2.

*/

```
public int integerBreak(int n) {
if (n < 3)
return 1;
if (n == 3)
return 2;
if (n % 3 == 0)
return (int) Math.pow(3, n / 3);
if (n % 3 == 1)
return 2 * 2 * ((int) Math.pow(3, (n - 4) / 3));
return 2 * ((int) Math.pow(3, (n - 2) / 3));
}
```