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:
nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 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:
nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.Adding these gives 4 + 4 + 4 = 12.
Constraints:
1 <= n == nums.length <= 5 * 1040 <= nums[i] <= 1091 <= k <= min(105, n * (n + 1) / 2)class Solution {
private class SegmentTree {
int[][] tree;
int[] nums;
SegmentTree(int n, int[] nums) {
this.tree = new int[4 * n][2];
this.nums = nums;
}
void build(int idx, int lt, int rt) {
if (lt == rt) {
tree[idx][0] = tree[idx][1] = nums[lt];
return;
}
int mid = (lt + rt) / 2;
build(2 * idx + 1, lt, mid);
build(2 * idx + 2, mid + 1, rt);
tree[idx] = new int[] { Math.max(tree[2 * idx + 1][0], tree[2 * idx + 2][0]),
Math.min(tree[2 * idx + 1][1], tree[2 * idx + 2][1]) };
}
int[] query(int idx, int stlt, int strt, int lt, int rt) {
if (rt < stlt || lt > strt) // out of range
return new int[] { Integer.MIN_VALUE, Integer.MAX_VALUE };
if (lt <= stlt && rt >= strt) // partial query result
return tree[idx];
int stmid = (stlt + strt) / 2;
int[] n1 = query(2 * idx + 1, stlt, stmid, lt, rt);
int[] n2 = query(2 * idx + 2, stmid + 1, strt, lt, rt);
return new int[] { Math.max(n1[0], n2[0]), Math.min(n1[1], n2[1]) };
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int[] node : tree)
sb.append("[").append(Arrays.toString(node)).append("]");
return sb.toString();
}
}
public long maxTotalValue(int[] nums, int k) {
int n = nums.length;
SegmentTree st = new SegmentTree(n, nums);
st.build(0, 0, n - 1);
// System.out.println(st);
Queue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0] - b[1]) - (a[0] - a[1]));
for (int i = 0; i < n; i++) {
int[] node = st.query(0, 0, n - 1, i, n - 1);
pq.offer(new int[] { node[0], node[1], i, n - 1 });
}
long ans = 0l;
while (k-- > 0) {
int[] node = pq.poll();
ans += node[0] - node[1];
int lt = node[2], rt = node[3];
if (lt < rt) {
node = st.query(0, 0, n - 1, lt, rt - 1);
pq.offer(new int[] { node[0], node[1], lt, rt - 1 });
}
}
return ans;
}
}