#3743

Maximize Cyclic Partition Score

hard · 12.5% accepted · 48 likes · top 0%

array · dynamic programming

Description

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.

Solution