Ezvor

3691. Maximum Total Subarray Value II

HardArray Preparing judge… LeetCode

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 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)
ArrayGreedySegment TreeHeap (Priority Queue)

Hints

Hint 1
For fixed l, the sequence v(l,r)=max(nums[l..r])−min(nums[l..r]) is non-increasing as r moves left.
Hint 2
Build RMQs (sparse tables) for range max/min so each v(l,r) is queryable in O(1).
Hint 3
Use a max-heap with v(l,n-1) for all l; pop the largest k times, and after popping an entry from (l,r) push (l,r-1) if r>l.