解題說明
Integer Break
題目描述：
給定正整數 n（n >= 2），將它拆分為至少兩個正整數的和，使這些正整數的乘積最大化。回傳最大乘積。
解題思路： 數學方法：盡量將數字拆成 3，因為 3 的乘積效率最高。
數學推導：
- 若拆出 1，1 對乘積沒有貢獻，應避免。
- 若拆出 4 以上的數，可以再拆（4 = 2+2, 2×2 = 4；5 = 2+3, 2×3 = 6 > 5），所以只用 2 和 3。
- 比較 2 和 3：三個 2 的乘積 = 8，兩個 3 的乘積 = 9 (2+2+2 = 3+3 = 6)，所以 3 更優。
- 結論：盡量用 3，若餘數為 1 則拿一個 3 出來變成 2×2（因為 2×2 = 4 > 1×3 = 3）。
特例：n=2 → 1×1=1，n=3 → 1×2=2。
C++ 解法
複雜度分析
時間複雜度：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)。但需注意浮點數精度問題，建議用整數快速冪。
延伸思考
- 能否用數學嚴格證明「盡量拆 3」是最優策略？（提示：AM-GM 不等式）
- 若允許拆出 0 或負數，問題會如何改變？
- 若 n 非常大（如 n = 10^18），如何在 O(log n) 時間內求解？需要用到什麼技巧？