日期：2026年6月10日
LeetCode 題目連結：3691. Maximum Total Subarray Value II
解題想法
困難題，昨天的 3689. Maximum Total Subarray Value I 加強版，難度提升很多。首先要建立稀疏表 (Sparse Tables)，用 st_max[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最大值，用 st_min[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最小值。再用最大優先佇列 (max priority queue) $pq$ 儲存起點 $L = 0$ 到 $L = n-1$、終點皆為 $n-1$ 各區間的 `max_val - min_val`，從 $pq$ 之中取出 $k$ 個值。假設取出的區間為 $[L, R]$，先將值 $val$ 加到答案 $ans$ 之中，重新計算區間 $[L, R-1]$ 對應的值 val，再將 {val, L, R-1} 加入 $pq$ 之中。
Python 程式碼
Runtime: 3165 ms, beats 70.73%. Memory: 52.34 MB, beats 53.66%.
class Solution:
def maxTotalValue(self, nums: List[int], k: int) -> int:
import heapq
n = len(nums) # 長度
# 特例，nums 是空的或是 k 等於 0，回傳 0
if n == 0 or k == 0:
return 0
# 1. 預先計算 log2(0) ~ log2(n)
log_table = [0] * (n+1)
for i in range(2, n+1):
log_table[i] = log_table[i//2] + 1
log_max = log_table[n] + 1 # log2 的上限
# 2. 初始化 Sparse Tables，table[i][j] 代表長度 2**j、起點 i 的區間極值
st_max = [[0] * log_max for _ in range(n)]
st_min = [[0] * log_max for _ in range(n)]
for i in range(n):
st_max[i][0] = nums[i]
st_min[i][0] = nums[i]
# 3. 建立 Sparse Tables
for j in range(1, log_max): # 1 ~ log2(n)
step = 1 << (j - 1) # 2**(j-1)
for i in range(n - (1 << j) + 1): # 起點 i
st_max[i][j] = max(st_max[i][j-1], st_max[i + step][j-1])
st_min[i][j] = min(st_min[i][j-1], st_min[i + step][j-1])
# 4. 自訂區間查詢函式
def query(L, R):
length = R - L + 1
j = log_table[length]
max_val = max(st_max[L][j], st_max[R - (1 << j) + 1][j])
min_val = min(st_min[L][j], st_min[R - (1 << j) + 1][j])
return max_val - min_val
# 5. 初始化最大優先佇列
pq = []
for L in range(n): # 起點 L = 0 ~ L = n-1
val = query(L, n-1) # 取區間 [L, n-1] 極值
heapq.heappush(pq, (-val, L, n-1))
# 6. 取前 k 大的極值
ans = 0
for _ in range(k):
neg_val, L, R = heapq.heappop(pq)
ans += -neg_val
# 更新 pq，同一個起點 L，新的終點 R-1
if R > L:
new_val = query(L, R-1)
heapq.heappush(pq, (-new_val, L, R-1))
# 7. 回傳答案
return ans
