3826. Minimum Partition Score Hard

1/**
2 * [3826] Minimum Partition Score
3 *
4 * You are given an integer array nums and an integer k.
5 * Your task is to partition nums into exactly k <span data-keyword="subarray-nonempty">subarrays</span> and return an integer denoting the minimum possible score among all valid partitions.
6 * The score of a partition is the sum of the values of all its subarrays.
7 * The value of a subarray is defined as sumArr * (sumArr + 1) / 2, where sumArr is the sum of its elements.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [5,1,2,1], k = 2</span>
12 * Output: <span class="example-io">25</span>
13 * Explanation:
14 * 
15 * 	We must partition the array into k = 2 subarrays. One optimal partition is [5] and [1, 2, 1].
16 * 	The first subarray has sumArr = 5 and value = 5 &times; 6 / 2 = 15.
17 * 	The second subarray has sumArr = 1 + 2 + 1 = 4 and value = 4 &times; 5 / 2 = 10.
18 * 	The score of this partition is 15 + 10 = 25, which is the minimum possible score.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [1,2,3,4], k = 1</span>
23 * Output: <span class="example-io">55</span>
24 * Explanation:
25 * 
26 * 	Since we must partition the array into k = 1 subarray, all elements belong to the same subarray: [1, 2, 3, 4].
27 * 	This subarray has sumArr = 1 + 2 + 3 + 4 = 10 and value = 10 &times; 11 / 2 = 55.​​​​​​​
28 * 	The score of this partition is 55, which is the minimum possible score.
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">nums = [1,1,1], k = 3</span>
33 * Output: <span class="example-io">3</span>
34 * Explanation:
35 * 
36 * 	We must partition the array into k = 3 subarrays. The only valid partition is [1], [1], [1].
37 * 	Each subarray has sumArr = 1 and value = 1 &times; 2 / 2 = 1.
38 * 	The score of this partition is 1 + 1 + 1 = 3, which is the minimum possible score.
39 * </div>
40 *  
41 * Constraints:
42 * 
43 * 	1 <= nums.length <= 1000
44 * 	1 <= nums[i] <= 10^4
45 * 	1 <= k <= nums.length 
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/minimum-partition-score/
51// discuss: https://leetcode.com/problems/minimum-partition-score/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn min_partition_score(nums: Vec<i32>, k: i32) -> i64 {
57        
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_3826() {
69    }
70}
71