343. Integer Break

Let's first look at the case where an integer can be broken into two integers, so the product  = x(N-x). The maximal product is at x=N/2. Now let's see what integers need to break in order to achieve the largest product, i.e. (N/2)*(N/2) >= N => N >= 4. So the product must consists of factors that can't be broken. The largest non-break number is 3. However, there is a special case where 4 should be broken into 2*2 not 1*3. So the solution is as following in which line 8 and 12 take care of the special case.

1:  class Solution {  
2:  public:  
3:    int integerBreak(int n) {  
4:      if (n == 1) return 1;  
5:      if (n == 2) return 1;  
6:      if (n == 3) return 2;  
7:      int product = 1;  
8:      while (n > 4) {  
9:        product *= 3;  
10:        n -= 3;  
11:      }  
12:      product *= n;  
13:      return product;  
14:    }  
15:  };