3691. Maximum Total Subarray Value II

Description

You are given an integer array nums of length n and an integer k.

You must select exactly k distinct non-empty 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 of 3 - 1 = 2.
• Choose 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:

• Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
• Choose nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
• Choose 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 * 10​​​​​​​4
• 0 <= nums[i] <= 109
• 1 <= k <= min(105, n * (n + 1) / 2)

 

Solutions

Solution: Heap + Sparse Table

• Time complexity: O(nlogn+klogn)
• Space complexity: O(nlogn)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const maxTotalValue = function (nums, k) {
  const n = nums.length;
  const maxLog = 32 - Math.clz32(n);
  const maxSt = Array.from({ length: n }, () => new Array(maxLog).fill(0));
  const minSt = Array.from({ length: n }, () => new Array(maxLog).fill(0));
  const maxHeap = new MaxHeap(({ value }) => value);
  const visited = new Set();
  let result = 0;

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    maxSt[index][0] = num;
    minSt[index][0] = num;
  }

  for (let l = 1; l < maxLog; l++) {
    const half = 1 << (l - 1);

    for (let index = 0; index + half < n; index++) {
      const halfStart = index + half;

      maxSt[index][l] = Math.max(maxSt[index][l - 1], maxSt[halfStart][l - 1]);
      minSt[index][l] = Math.min(minSt[index][l - 1], minSt[halfStart][l - 1]);
    }
  }

  const queryMax = (l, r) => {
    const len = r - l + 1;
    const log = 31 - Math.clz32(len);
    const half = 1 << log;

    return Math.max(maxSt[l][log], maxSt[r - half + 1][log]);
  };

  const queryMin = (l, r) => {
    const len = r - l + 1;
    const log = 31 - Math.clz32(len);
    const half = 1 << log;

    return Math.min(minSt[l][log], minSt[r - half + 1][log]);
  };

  const pushSub = (l, r) => {
    if (l > r) return;

    const key = `${l},${r}`;

    if (visited.has(key)) return;

    const maxValue = queryMax(l, r);
    const minValue = queryMin(l, r);
    const value = maxValue - minValue;

    maxHeap.push({ value, l, r });
    visited.add(key);
  };

  pushSub(0, n - 1);

  while (maxHeap.size() && k) {
    const { value, l, r } = maxHeap.pop();

    result += value;
    pushSub(l + 1, r);
    pushSub(l, r - 1);
    k -= 1;
  }

  return result;
};