每日一题-2020729

题目

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

题解

其实就是剪绳子问题换了个样子。动态规划解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
object Solution {
def integerBreak(n: Int): Int = {
val array = Array.ofDim[Int](n + 1)
array(1) = 1

for (i <- 2 until n+1) {
for (j <- 1 until i) {
array(i) = Math.max(array(i), Math.max(j * (i - j), j * array(i - j)))
}
}
array(n)


}
}
使用搜索:谷歌必应百度