3691. Maximum Total Subarray Value II Hard

1/**
2 * [3691] Maximum Total Subarray Value II
3 *
4 * You are given an integer array nums of length n and an integer k.
5 * You must select exactly k distinct non-empty <span data-keyword="subarray-nonempty">subarrays</span> nums[l..r] of nums. Subarrays may overlap, but the exact same subarray (same l and r) cannot be chosen more than once.
6 * The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).
7 * The total value is the sum of the values of all chosen subarrays.
8 * Return the maximum possible total value you can achieve.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [1,3,2], k = 2</span>
13 * Output: <span class="example-io">4</span>
14 * Explanation:
15 * One optimal approach is:
16 * 
17 * 	Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
18 * 	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.
19 * 
20 * Adding these gives 2 + 2 = 4.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">nums = [4,2,5,1], k = 3</span>
25 * Output: <span class="example-io">12</span>
26 * Explanation:
27 * One optimal approach is:
28 * 
29 * 	Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
30 * 	Choose nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
31 * 	Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.
32 * 
33 * Adding these gives 4 + 4 + 4 = 12.
34 * </div>
35 *  
36 * Constraints:
37 * 
38 * 	1 <= n == nums.length <= 5 * 10^​​​​​​​4
39 * 	0 <= nums[i] <= 10^9
40 * 	1 <= k <= min(10^5, n * (n + 1) / 2)
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/maximum-total-subarray-value-ii/
46// discuss: https://leetcode.com/problems/maximum-total-subarray-value-ii/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn max_total_value(nums: Vec<i32>, k: i32) -> i64 {
52        
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_3691() {
64    }
65}
66