3077. Maximum Strength of K Disjoint Subarrays Hard

1/**
2 * [3077] Maximum Strength of K Disjoint Subarrays
3 *
4 * You are given an array of integers nums with length n, and a positive odd integer k.
5 * Select exactly k disjoint <span data-keyword="subarray-nonempty">subarrays</span> sub1, sub2, ..., subk from nums such that the last element of subi appears before the first element of sub{i+1} for all 1 <= i <= k-1. The goal is to maximize their combined strength.
6 * The strength of the selected subarrays is defined as:
7 * strength = k * sum(sub1)- (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... - 2 * sum(sub{k-1}) + sum(subk)
8 * where sum(subi) is the sum of the elements in the i-th subarray.
9 * Return the maximum possible strength that can be obtained from selecting exactly k disjoint subarrays from nums.
10 * Note that the chosen subarrays don't need to cover the entire array.
11 *  
12 * <strong class="example">Example 1:
13 * Input: <span class="example-io">nums = [1,2,3,-1,2], k = 3</span>
14 * Output: <span class="example-io">22</span>
15 * Explanation:
16 * The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and nums[4..4]. The strength is calculated as follows:
17 * strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22
18 *  
19 * <strong class="example">Example 2:
20 * Input: <span class="example-io">nums = [12,-2,-2,-2,-2], k = 5</span>
21 * Output: <span class="example-io">64</span>
22 * Explanation:
23 * The only possible way to select 5 disjoint subarrays is: nums[0..0], nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is calculated as follows:
24 * strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64
25 * <strong class="example">Example 3:
26 * Input: <span class="example-io">nums = [-1,-2,-3], k = </span>1
27 * Output: <span class="example-io">-1</span>
28 * Explanation:
29 * The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.
30 *  
31 * Constraints:
32 * 
33 * 	1 <= n <= 10^4
34 * 	-10^9 <= nums[i] <= 10^9
35 * 	1 <= k <= n
36 * 	1 <= n * k <= 10^6
37 * 	k is odd.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/maximum-strength-of-k-disjoint-subarrays/
43// discuss: https://leetcode.com/problems/maximum-strength-of-k-disjoint-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn maximum_strength(nums: Vec<i32>, k: i32) -> i64 {
49        
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_3077() {
61    }
62}
63