#3826
Minimum Partition Score
hard · 34% accepted · 45 likes · top 11%
array · divide and conquer · dynamic programming · queue · prefix sum · monotonic queue
Description
You are given an integer array nums and an integer k.
Your task is to partition nums into exactly k subarrays and return an integer denoting the minimum possible score among all valid partitions.
The score of a partition is the sum of the values of all its subarrays.
The value of a subarray is defined as sumArr * (sumArr + 1) / 2, where sumArr is the sum of its elements.
Solution