Maximum Total Subarray Range from Distinct Choices

### Problem You are given an integer array `nums` and an integer `k`. Select exactly `k` nonempty contiguous subarrays. Selected subarrays may overlap, but **every selected endpoint pair `(l,r)` must be distinct**. Two subarrays with the same values are still different choices if their endpoint pairs differ. A subarray's value is its largest element minus its smallest element. Return the greatest possible sum of the values of the `k` selected subarrays. ```cpp class Solution { public: long long maxTotalValue(vector<int>& nums, int k); }; ``` ### Examples **Example 1:** ```text Input: nums = [5,1,4], k = 3 Output: 11 Explanation: Select endpoint pairs (0,1), (0,2), and (1,2). Their values are 4, 4, and 3, for a total of 11. The remaining three subarrays are single elements of value zero, so no better three distinct choices exist. ``` **Example 2:** ```text Input: nums = [7,7], k = 3 Output: 0 Explanation: The three available endpoint pairs are (0,0), (1,1), and (0,1). They are distinct even though both one-element subarrays contain 7. Every value is zero, and exactly three subarrays are selected. ``` ### Constraints - `1 <= n == nums.length <= 50000`. - `0 <= nums[i] <= 1000000000`. - `1 <= k <= min(100000, n * (n + 1) / 2)`. ### Clarifying Questions - May the same endpoints be used twice? No. - May two selected subarrays overlap? Yes. - Do equal subarray values make the selections identical? No; identity is determined by endpoints. - Does “exactly k” still apply when all remaining subarray values are zero? Yes. - Must selected endpoints be returned? No, only their maximum total value. ### What a Strong Answer Covers - Distinct endpoint pairs, permitted overlap, and the exact selection count. - Correct treatment of tied values, repeated array entries, and zero-valued subarrays. - A proof of optimality and completeness of the considered choices. - The full `n` and `k` bounds, including suitable arithmetic and memory use. ### Follow-up Questions - What result is possible when all array values are equal? - How would returning the chosen endpoint pairs change the output-space requirement? ```hint Merge ordered candidate sequences For a fixed left endpoint, shortening the right endpoint cannot increase the subarray's range value. Start with the largest candidate from each left endpoint, and maintain the best remaining head across those sequences. Fast range-minimum and range-maximum queries make the candidate values available without rescanning each range. ```