LeetCode Integer Break

LeetCode Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

Hint:

  1. There is a simple O(n) solution to this problem.
  2. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

给定一个数n,要求把其拆分成至少两个数的和,使得他们的乘积最大。

数学题,没啥思路,参考网上题解

把0~10的结果先列出来找找规律:

  • 0:0
  • 1:0
  • 2:1=1*1
  • 3:2=2*1
  • 4:4=2*2
  • 5:6=3*2
  • 6:9=3*3
  • 7:12=3*4
  • 8:18=3*3*2
  • 9:27=3*3*3
  • 10:36=3*3*4

可以发现,n从5开始,都至少分解出来一个3,可以推断的是,当n=11时,在10的基础上,把最后一个4改成5,然后5又可以分解成3*2,所以11=3+3+3+2使得乘积最大。

4只能分解出2+2,1+3的乘积是3小于2*2;5可以分解出3+2,所以也有3。也就是说,当n大于4时,不断分解出3来,直到剩余的数小于4为止。所以有如下代码:

class Solution {
public:
	int integerBreak(int n) {
		if (n <= 3)return n - 1;
		int ans = 1;
		while (n > 4) {
			ans *= 3;
			n -= 3;
		}
		return ans*n;
	}
};

本代码提交AC,用时0MS。

再次观察上述规律,n=10的结果是n=7=10-3的结果乘以3;n=9的结果也是n=6=9-3的结果乘以3。可以推断,n的结果是(n-3)的结果乘以3。所以先列出前几个结果,后面的结果通过其前3的结果乘以3推导得到。代码如下:

class Solution {
public:
	int integerBreak(int n) {
		vector<int> dp = { 0,0,1,2,4,6,9 };
		for (int i = 7; i <= n; ++i)dp.push_back(dp[i - 3] * 3);
		return dp[n];
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *