3743. Maximize Cyclic Partition Score Hard

1/**
2 * [3743] Maximize Cyclic Partition Score
3 *
4 * You are given a cyclic array nums and an integer k.
5 * Partition nums into at most k <span data-keyword="subarray-nonempty">subarrays</span>. As nums is cyclic, these subarrays may wrap around from the end of the array back to the beginning.
6 * The range of a subarray is the difference between its maximum and minimum values. The score of a partition is the sum of subarray ranges.
7 * Return the maximum possible score among all cyclic partitions.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,2,3,3], k = 2</span>
12 * Output: <span class="example-io">3</span>
13 * Explanation:
14 * 
15 * 	Partition nums into [2, 3] and [3, 1] (wrapped around).
16 * 	The range of [2, 3] is max(2, 3) - min(2, 3) = 3 - 2 = 1.
17 * 	The range of [3, 1] is max(3, 1) - min(3, 1) = 3 - 1 = 2.
18 * 	The score is 1 + 2 = 3.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [1,2,3,3], k = 1</span>
23 * Output: <span class="example-io">2</span>
24 * Explanation:
25 * 
26 * 	Partition nums into [1, 2, 3, 3].
27 * 	The range of [1, 2, 3, 3] is max(1, 2, 3, 3) - min(1, 2, 3, 3) = 3 - 1 = 2.
28 * 	The score is 2.
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">nums = [1,2,3,3], k = 4</span>
33 * Output: <span class="example-io">3</span>
34 * Explanation:
35 * Identical to Example 1, we partition nums into [2, 3] and [3, 1]. Note that nums may be partitioned into fewer than k subarrays.
36 * </div>
37 *  
38 * Constraints:
39 * 
40 * 	1 <= nums.length <= 1000
41 * 	1 <= nums[i] <= 10^9
42 * 	1 <= k <= nums.length
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/maximize-cyclic-partition-score/
48// discuss: https://leetcode.com/problems/maximize-cyclic-partition-score/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn maximum_score(nums: Vec<i32>, k: i32) -> i64 {
54        
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3743() {
66    }
67}
68