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.

题目地址:leetcode Integer Break 

题意:给定整数n(n>=2),把它分解为若干个整数的和,且这些整数的乘积最大。

思路:

一觉起来发现李大牛出题了。。

这种题肯定是DP嘛

设dp[i]为最大的乘积值,水水的O(n^2)代码如下:

 

但是hint说可以O(n)!

在n >3的情况下,我们处理一个数拆分成2,要么拆分成3,(4的话相当于2个2 , 拆成1的话乘积太小了),所以就可以这样啦:

 

然而还可以继续优化:

可以说,拆成3的比拆成2的乘积大。 比如6的时候 2*2*2 < 3*3

我们希望能尽可能的拆成3,然后才是2.

所以,如果

  • n % 3 == 0:  那么全部拆成3
  • n % 3 == 1:  2个2剩下的为3    4*3^(x-1) > 1*3^x
  • n % 3 == 2:  1个2剩下的为3

 

 

 

 

本题是leetcode 343 Integer Break 题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Integer Break
本文地址:https://www.hrwhisper.me/leetcode-integer-break/

听说长得好看的已经打赏了

Leetcode , , . permalink.

Leave a Reply

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