HardRating 2943

2945. Find Maximum Non-decreasing Array Length

arraybinary-searchdynamic-programmingstackqueuemonotonic-stackmonotonic-queue

解題說明

Find Maximum Non-decreasing Array Length

題目描述：給定一個整數陣列 nums，你可以執行任意次操作：選擇相鄰的兩個元素，將它們合併為一個元素（其值為兩者之和）。目標是讓最終陣列為非遞減（non-decreasing），並使最終陣列的長度最大化。

解題思路：使用動態規劃搭配前綴和。令 dp[i] 表示考慮前 i 個元素時，最終非遞減陣列的最大長度。關鍵觀察：若最後一個「合併段」為 nums[j+1..i]（前綴和差 pre[i] - pre[j]），則需要 pre[i] - pre[j] >= last[j]（last[j] 是 dp[j] 方案中最後一段的和）。等價轉換後條件變為 pre[i] >= pre[j] + last[j]，令 val[j] = pre[j] + last[j]，即找最大的 j 使 val[j] <= pre[i]。由於 val 非遞減，可用單調雙端佇列維護候選，達到 O(n) 整體時間。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多進出雙端佇列一次，前綴和計算亦為線性。

空間複雜度：O(n) — 前綴和、DP 陣列與雙端佇列各使用 O(n) 空間。

虛擬碼

1. Compute prefix sums pre[0..n]
2. Initialize dp[0] = 0, last[0] = 0
3. Create monotonic deque with index 0
4. For i = 1 to n:
   a. Pop from front while dq has >1 element and pre[dq[1]] + last[dq[1]] <= pre[i]
   b. Set j = dq.front(); dp[i] = dp[j] + 1; last[i] = pre[i] - pre[j]
   c. Pop from back while pre[dq.back()] + last[dq.back()] >= pre[i] + last[i]
   d. Push i to back of deque
5. Return dp[n]

其他解法

二分搜尋 + DP O(n log n)：不使用單調佇列，改為在 val 陣列上二分搜尋找最大的 j 使 val[j] <= pre[i]。實作簡單但時間複雜度多一個 log 因子。

貪心分段 O(n²)：嘗試每個分割點暴力搜尋最小段和限制 — 正確但在大型輸入上超時。

延伸思考

如果要求最終陣列嚴格遞增（strictly increasing），演算法需要如何修改？
如果每次操作只能合併連續的最多 k 個元素（而非任意相鄰兩個），最大長度會如何變化？
能否同時輸出最大長度與一組具體的合併方案？

解題說明

Find Maximum Non-decreasing Array Length

虛擬碼

1. Compute prefix sums pre[0..n] 2. Initialize dp[0] = 0, last[0] = 0 3. Create monotonic deque with index 0 4. For i = 1 to n: a. Pop from front while dq has >1 element and pre[dq[1]] + last[dq[1]] <= pre[i] b. Set j = dq.front(); dp[i] = dp[j] + 1; last[i] = pre[i] - pre[j] c. Pop from back while pre[dq.back()] + last[dq.back()] >= pre[i] + last[i] d. Push i to back of deque 5. Return dp[n]