LeetCode 解題筆記：3691. Maximum Total Subarray Value II

作者：王一哲
日期：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)  # 
            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

C++ 程式碼

Runtime: 731 ms, beats 55.64%. Memory: 383.89 MB, beats 7.25%.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        int n = (int)nums.size();  // 長度
        /* 特例，回傳 0 */
        if (n == 0 || k == 0) return 0;

        /* 1. 建表，預計算 log2(0) ~ log2(n) */
        vector<int> table (n+1, 0);  // log2(0) ~ log2(n)
        for(int i=2; i<=n; i++) {
            table[i] = table[i/2] + 1;
        }
        int log_max = table[n] + 1;
        
        /* 2. 初始化 Sparse Tables，table[i][j] 代表長度 2**j、起點 i 的區間極值 */
        vector<vector<long long>> st_max(n, vector<long long> (log_max, 0));
        vector<vector<long long>> st_min(n, vector<long long> (log_max, 0));
        st_min.assign(n, vector<long long> (log_max, 0));
        for(int i=0; i<n; i++) {
            st_max[i][0] = nums[i];
            st_min[i][0] = nums[i];
        }

        /* 3. 建立 Sparse Tables */
        for(int j = 1; j < log_max; j++) {
            int step = 1 << (j - 1);
            for(int i = 0; i <= n - (1 << j); 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. 自訂區間查詢函式 */
        auto query = [&](int L, int R) {
            int length = R - L + 1;
            int j = table[length];
            long long max_val = max(st_max[L][j], st_max[R - (1 << j) + 1][j]);
            long long min_val = min(st_min[L][j], st_min[R - (1 << j) + 1][j]);
            return max_val - min_val;
        };

        /* 5. 初始化最大優先佇列 */
        priority_queue<tuple<int, int, int>> pq;
        for(int L = 0; L < n; L++) {
            int val = query(L, n-1);
            pq.push({val, L, n-1});
        }

        /* 6. 取前 k 大的極值 */
        long long ans = 0;
        for(int i=0; i<k; i++) {
            auto [val, L, R] = pq.top();
            pq.pop();
            ans += val;  // 直接加正值
            // 更新 pq，同一個起點 L，新的終點 R-1
            if (L < R) {
                int new_val = query(L, R-1);
                pq.push({new_val, L, R-1});
            }
        }
        return ans;
    }
};