class SegTree { int n; vector maxv, minv; public: SegTree(const vector& nums) { n = nums.size(); maxv.resize(4 * n); minv.resize(4 * n); build(1, 0, n - 1, nums); } void build(int node, int l, int r, const vector& nums) { if (l == r) { maxv[node] = minv[node] = nums[l]; return; } int m = l + (r - l) / 2; build(node * 2, l, m, nums); build(node * 2 + 1, m + 1, r, nums); maxv[node] = max(maxv[node * 2], maxv[node * 2 + 1]); minv[node] = min(minv[node * 2], minv[node * 2 + 1]); } pair query(int node, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return {maxv[node], minv[node]}; int m = l + (r - l) / 2; pair res = {-1e9, 1e9}; if (ql <= m) { auto left = query(node * 2, l, m, ql, qr); res.first = max(res.first, left.first); res.second = min(res.second, left.second); } if (qr > m) { auto right = query(node * 2 + 1, m + 1, r, ql, qr); res.first = max(res.first, right.first); res.second = min(res.second, right.second); } return res; } long long getVal(int l, int r) { auto res = query(1, 0, n - 1, l, r); return (long long)res.first - res.second; } }; class Solution { public: long long maxTotalValue(vector& nums, int k) { int n = nums.size(); SegTree st(nums); priority_queue> pq; for (int i = 0; i < n; i++) { pq.push({st.getVal(i, n - 1), i, n - 1}); } long long ans = 0; while (k--) { auto top = pq.top(); pq.pop(); ans += top[0]; int l = top[1], r = top[2]; if (r > l) { pq.push({st.getVal(l, r - 1), l, r - 1}); } } return ans; } };

Time Complexity

Space Complexity