每日一题-2020729

题目

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

题解

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

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)
 

    }
}