Leetcode 343 整数拆分

题目概述

Leetcode 343

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.

Constraints:

• 2 <= n <= 58

思路

根据题意，对于一个给定的正整数 $n$ , 有:

$$n = \sum_{i=1}^k n_i \qquad (1 \leq k \leq n, \quad n_k \in \boldsymbol{Z^+})$$

现在需要求:

$$max(\prod_{i=1}^k n_i)$$

注意到这里的任意 $n_i$ 均为正整数，所以根据均值不等式，有：

$$\begin{aligned} \sqrt[k]{n_1 n_2 \cdots n_k} \quad &\leq \quad \frac{n_1 + n_2 + \cdots + n_k}{k} \\[5mm] n_1 n_2 \cdots n_k \quad &\leq \quad \left(\frac{n_1 + n_2 + \cdots + n_k}{k}\right) ^ k \end{aligned}$$

当且仅当 $n_1 = n_2 = \cdots = n_k$ 时不等式取等号，也即乘积取得最大值。但是在这道题的语境下 $n_i$ 为正整数，直接取等的话无法保证满足这个条件。不过，我们可以先按照这个思路去求得 $k$ 取什么值，也即原本的整数 $n$ 在被均分成多少个数的时候它们的乘积能得到最大值。令:

$$f(k) = n_1 n_2 \cdots n_k = \left(\frac{n}{k}\right)^k \qquad (1 \leq k \leq n)$$

想要求 $f(k)_{max}$ , 利用对数微分法求导:

$$\begin{aligned} & log f(k) = k log (\frac{n}{k}) = k (log n - log k) \\[3mm] & \frac{f'(k)}{f(k)} = (log n - log k) - \frac{1}{k} \times k = log n - log k - 1 \\[3mm] & f'(k) = \left(\frac{n}{k}\right) ^ k (log n - log k - 1) \end{aligned}$$

令 $f'(k) = 0$ , 有:

$$\begin{aligned} & log n - log k - 1 = 0 \\[3mm] & log k = log n - 1 = log n - log e = log \left(\frac{n}{e}\right) \\[3mm] \therefore \quad & k = \frac{n}{e} \end{aligned}$$

考察 $f(k)$ 增减性:

$$\begin{aligned} & 1 \leq k \leq \frac{n}{e} \quad , \quad f'(k) > 0 \\[3mm] & k > \frac{n}{e} \quad , \quad f'(k) < 0 \end{aligned}$$

所以 $f(k)$ 在 $k = \large \frac{n}{e}$ 时取得最大值, 此时每一个乘数的值均为 $e$ 。但题目里要求乘数必须为正整数，所以这还不是最终的答案。这里虽然没有严谨的证明，但是我们可以近似地认为只要分离出的乘数 $n_i$ 越接近 $e$ , 那么最终这些乘数的乘积越大。而最接近 $e$ 的正整数为3，所以问题似乎就转变成: 将一个正整数尽可能多地分成正整数3的和。

但这样还不对。我们可以设想一下 $n = 7$ 时，如果只是尽可能多地分离出3，那么最终的结果为:

$$7 = 3 + 3 + 1 \quad , \quad 3 \times 3 \times 1 = 9$$

然而我们还能得到:

$$7 = 3 + 4 \quad , \quad 3 \times 4 = 12$$

显然12是大于9的。这里其实稍加思考便可以得知问题出在了哪。当我们将一个数不断地拆分为3和剩余的部分，那么根据这个数除以3得到的余数，最终会有如下三种情况:

• 余数为0, 刚好将3分离完的最理想情况，无需再做讨论。
• 余数为2, 那么最后剩余的部分为2或5 (少分离一个3), 如果考虑与 $e \approx 2.71828$ 的接近程度，那么显然前者更优。（两种分离方式在倒数第三项为止的乘积相同, 剩下要做的比较便是(2, 3)与5哪一种与 $e$ 的差值最小, 显然前者更小）
• 余数为1, 与上一种情况类似，这里最后剩余的部分为(1, 3)或(2, 2), 比较与 $e$ 的差值的话后者更优。

到这里为止，问题基本就分析完毕了。最后还需考虑一种情况，那便是 $n \leq 3$ 的时候。这里可以作为特判, 无外乎两种情况:

• 2 = 1 + 1, 结果为1
• 3 = 1 + 2, 结果为2

总结一下思路: 在$n > 4$时，尽可能多地分离出3。

代码实现

1. 在 $n > 4$ 时，尽可能多地分离出3

   Time complexity: O(n)

   Space complexity: O(1)

   class Solution:
       def integerBreak(self, n: int) -> int:
           if n <= 3:
               return n - 1
   
           ans = 1
           while n > 4:
               ans *= 3
               n -= 3
   
           return ans * n

   

2. 优化, 根据 $n$ 的值直接可以计算出分离出来的3的个数, 按照其除以3的余数分类讨论即可

   Time complexity: O(logn)

   Space complexity: O(1)

   class Solution:
       def integerBreak(self, n: int) -> int:
           if n <= 3:
               return n - 1
   
           if n % 3 == 0:
               return 3 ** (n // 3)
           elif n % 3 == 1:
               return 3 ** ((n - 4) // 3) * 4
           else:
               return 3 ** ((n - 2) // 3) * 2
               

   注： 乘方运算的时间复杂度为 **O(logn)**