leetcode-剪绳子 I-57

题目要求

  给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路

  如果想要面积最大，我们要考虑怎样的组合面积最大，那就是尽可能多的分出长度为3，如果余数为1的情况下，我们可以把最后4米换成2 *2的形式，这样这个题的解法就是O(1)的。

代码实现

class Solution {
public:
	int cuttingRope(int n) {
		if (n == 1 || n == 2)
			return 1;
		if (n == 3)
			return 2;
		int a = 0;
		int result = 1;

		if (n % 3 == 0)
		{
			a = n / 3;
			while (a--)
			{
				result *= 3;
			}
		}

		if (n % 3 == 1)
		{
			a = (n / 3) - 1;
			while (a)
			{
				result = 3 * result;
				a--;
			}
			result = result * 4;
		}

		if (n % 3 == 2)
		{
			a = n / 3;
			while (a)
			{
				result *= 3;
				a--;
			}
			result = result * 2;
		}
		return result;
	}
};