題目描述:
給定正整數 n(n >= 2),將它拆分為至少兩個正整數的和,使這些正整數的乘積最大化。回傳最大乘積。
解題思路: 數學方法:盡量將數字拆成 3,因為 3 的乘積效率最高。
數學推導:
特例:n=2 → 1×1=1,n=3 → 1×2=2。
時間複雜度:O(n/3) = O(n) — 每次減去 3,迴圈約 n/3 次。實務上可用 pow 做到 O(1)。
空間複雜度:O(1) — 只使用常數額外空間。
1. If n == 2, return 1; if n == 3, return 2 2. Initialize result = 1 3. While n > 4: a. result = result * 3 b. n = n - 3 4. result = result * n (remaining n is 2, 3, or 4) 5. Return result
動態規劃 O(n²):定義 dp[i] 為將 i 拆分後的最大乘積。轉移式:dp[i] = max(j * max(i-j, dp[i-j])) 對所有 1 <= j < i。其中 max(i-j, dp[i-j]) 表示剩餘部分可以不繼續拆分。空間 O(n)。相較數學法更通用,但效率較低。
快速冪 O(log n):計算 3 的 n/3 次方,根據餘數調整。用 pow(3, n/3) 配合餘數處理,可達到 O(log n) 或甚至 O(1)。但需注意浮點數精度問題,建議用整數快速冪。