【剑指 Offer 14- II. 剪绳子 II】(剪绳子I大数)

 【解题思路】

（1）n = 2时，ans = 1;

（2）n = 3时，ans = 2;

（3）n = 4时，ans = 2*2 = 4;

（4）n = 5时，ans = 2*3 = 6 > 5

       观察发现，当n >= 4时，分割后可以达到比n更大的乘积；而n < 4时，ans < n，不剪的结果更大。所以绳子分割为1、2、3时乘积最大。

       分割为1时，对乘积的贡献是1；分割为2时，对乘积的贡献是根号下2；分割为3时，对乘积的贡献是三次根号下3。可见绳子分割为3时乘积最大。将长度为n的绳子尽可能分割为长度为3。

如果n%3 == 1，2*2 > 1*3，所以拿出一个3，和1组成2*2可以得到做大乘积。如果n%3 == 2，在取出尽可能多的3后，再乘余数2即为最大乘积。

class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        
        long ans = 1;
        int m = n/3;
        if(n % 3 == 1)
        {
            m = m-1;
            for(int i = 0; i < m; i++)
            {
                ans = (ans*3) % 1000000007;
            }
            ans = (ans * 4) % 1000000007;
        }
        else if(n % 3 == 2)
        {
            for(int i = 0; i < m; i++)
            {
                ans = (ans*3) % 1000000007;
            }
            ans = (ans * 2) % 1000000007;
        }
        else{
            for(int i = 0; i < m; i++)
            {
                ans = (ans*3) % 1000000007;
            }
        }
       return (int)ans;
    }
}