Description
You are given an integer array nums of length n and an integer k.
You must select exactly k distinct subarrays nums[l..r] of nums. Subarrays may overlap, but the exact same subarray (same l and r) cannot be chosen more than once.
The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).
The total value is the sum of the values of all chosen subarrays.
Return the maximum possible total value you can achieve.
Example 1:
Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
One optimal approach is:
- Choose
nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of3 - 1 = 2. - Choose
nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also3 - 1 = 2.
Adding these gives 2 + 2 = 4.
Example 2:
Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
One optimal approach is:
- Choose
nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of5 - 1 = 4. - Choose
nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also4. - Choose
nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again4.
Adding these gives 4 + 4 + 4 = 12.
Constraints:
1 <= n == nums.length <= 5 * 1040 <= nums[i] <= 1091 <= k <= min(105, n * (n + 1) / 2)
Solutions
This code efficiently finds the sum of the top k largest “value ranges” from subarrays, where a subarray’s value is its maximum number minus its minimum number. First, it builds a sparse table, which is a lookup structure that can quickly answer: “what is the max minus min in nums[left...right)?” Then, for every starting index i, it puts the value of the subarray from i to the end of the array into a max-priority queue, along with its left and right boundaries. The queue always gives the currently largest subarray value. Each time the code takes the largest value, it adds it to res, then shrinks that same subarray from the right by one position and puts the smaller version back into the queue, because that may still be one of the next best values. It repeats this until it has taken k values or there are no positive values left. In short, the sparse table makes range calculations fast, and the priority queue helps repeatedly pick the next biggest subarray max-min difference without generating and sorting every possible subarray value upfront.
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
const maxTotalValue = (nums, k) => {
const n = nums.length;
const LUT = sparseTable(nums);
const pq = new PriorityQueue(([a], [b]) => b - a);
let res = 0;
for (let i = 0; i < n; i++) {
pq.enqueue([LUT.query(i, n), i, n]);
}
while (pq.front()[0] > 0 && k > 0) {
const [v, l, r] = pq.dequeue();
res += v;
pq.enqueue([LUT.query(l, r - 1), l, r - 1]);
k--;
}
return res;
};
const sparseTable = nums => {
const n = nums.length;
const bitW = 32 - Math.clz32(n);
const min = Array.from({ length: bitW }, () => Array(n));
const max = Array.from({ length: bitW }, () => Array(n));
for (let i = 0; i < n; i++) {
min[0][i] = max[0][i] = nums[i];
}
for (let i = 1; i < bitW; i++) {
for (let j = 0; j + (1 << i) <= n; j++) {
min[i][j] = Math.min(min[i - 1][j], min[i - 1][j + (1 << (i - 1))]);
max[i][j] = Math.max(max[i - 1][j], max[i - 1][j + (1 << (i - 1))]);
}
}
return {
query: (left, right) => {
const k = 31 - Math.clz32(right - left);
return Math.max(max[k][left], max[k][right - (1 << k)]) -
Math.min(min[k][left], min[k][right - (1 << k)]);
}
};
};