Maximize Cyclic Partition Score
You are given a cyclic array nums and an integer k.
Partition nums into at most k subarrays. As nums is cyclic, these subarrays may wrap around from the end of the array back to the beginning.
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.
Return the maximum possible score among all cyclic partitions.
Example 1
Input
nums = [1,2,3,3], k = 2Output
3Partition
nums into [2, 3] and [3, 1] wrapped around, whose ranges are 1 and 2 for a total score of 3.Example 2
Input
nums = [1,2,3,3], k = 1Output
2Partition
nums into [1, 2, 3, 3], whose range is 3 - 1 = 2, so the score is 2.Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^9
- 1 <= k <= nums.length