Segment Tree + Max-Heap Approach
This visual builds the segment tree node by node, then uses a Max-Heap to efficiently extract the top k subarrays by value max(nums[l..r]) - min(nums[l..r]) without enumerating all O(n²) possibilities.
Array nums
Segment Tree (Range Max/Min Queries)
Max-Heap (Current State)
Selected Subarrays (0/3)
Step log
| 1 | struct Node { int mx, mn; }; |
| 2 | vector<Node> seg; |
| 3 | |
| 4 | void build(vector<int>& a, int idx, int l, int r) { |
| 5 | if (l == r) { seg[idx] = {a[l], a[l]}; return; } |
| 6 | int mid = (l + r) / 2; |
| 7 | build(a, idx*2, l, mid); |
| 8 | build(a, idx*2+1, mid+1, r); |
| 9 | seg[idx].mx = max(seg[idx*2].mx, seg[idx*2+1].mx); |
| 10 | seg[idx].mn = min(seg[idx*2].mn, seg[idx*2+1].mn); |
| 11 | } |
| 12 | |
| 13 | Node query(int idx, int l, int r, int ql, int qr) { |
| 14 | if (r < ql || l > qr) return {-INF, INF}; |
| 15 | if (ql <= l && r <= qr) return seg[idx]; |
| 16 | int mid = (l + r) / 2; |
| 17 | return { max(query(2*idx, l, mid, ql, qr).mx, |
| 18 | query(2*idx+1, mid+1, r, ql, qr).mx), |
| 19 | min(query(2*idx, l, mid, ql, qr).mn, |
| 20 | query(2*idx+1, mid+1, r, ql, qr).mn) }; |
| 21 | } |
| 22 | |
| 23 | long long maxTotalValue(vector<int>& nums, int k) { |
| 24 | int n = nums.size(); |
| 25 | seg.assign(4*n, {0,0}); |
| 26 | build(nums, 1, 0, n-1); |
| 27 | priority_queue<tuple<long long, int, int>> pq; |
| 28 | |
| 29 | // 1. Initialize heap with [l, n-1] for all l |
| 30 | for (int l = 0; l < n; l++) { |
| 31 | Node res = query(1, 0, n-1, l, n-1); |
| 32 | pq.push({res.mx - res.mn, l, n-1}); |
| 33 | } |
| 34 | |
| 35 | long long ans = 0; |
| 36 | // 2. Extract top k elements |
| 37 | while (k--) { |
| 38 | auto [val, l, r] = pq.top(); pq.pop(); |
| 39 | ans += val; |
| 40 | if (r > l) { |
| 41 | Node nextRes = query(1, 0, n-1, l, r-1); |
| 42 | pq.push({nextRes.mx - nextRes.mn, l, r-1}); |
| 43 | } |
| 44 | } |
| 45 | return ans; |
| 46 | } |
Test Cases
Basic case with overlapping subarrays
Input Configuration
For clarity, keep n ≤ 10 so node diagrams stay readable.
Animation Controls
Complexity Analysis
O(n log n + k log n)
O(n)
Uses a Segment Tree for O(log n) range max/min queries and a Max-Heap to efficiently find the top k subarrays without enumerating all O(n²) possibilities.