2025. Maximum Number of Ways to Partition an Array Hard

1/**
2 * [2025] Maximum Number of Ways to Partition an Array
3 *
4 * You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:
5 * 
6 * 	1 <= pivot < n
7 * 	nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
8 * 
9 * You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.
10 * Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.
11 *  
12 * Example 1:
13 * 
14 * Input: nums = [2,-1,2], k = 3
15 * Output: 1
16 * Explanation: One optimal approach is to change nums[0] to k. The array becomes [<u>3</u>,-1,2].
17 * There is one way to partition the array:
18 * - For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.
19 * 
20 * Example 2:
21 * 
22 * Input: nums = [0,0,0], k = 1
23 * Output: 2
24 * Explanation: The optimal approach is to leave the array unchanged.
25 * There are two ways to partition the array:
26 * - For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
27 * - For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.
28 * 
29 * Example 3:
30 * 
31 * Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
32 * Output: 4
33 * Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,<u>-33</u>,-20,-15,15,-16,7,19,-10,0,-13,-14].
34 * There are four ways to partition the array.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	n == nums.length
40 * 	2 <= n <= 10^5
41 * 	-10^5 <= k, nums[i] <= 10^5
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array/
47// discuss: https://leetcode.com/problems/maximum-number-of-ways-to-partition-an-array/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn ways_to_partition(nums: Vec<i32>, k: i32) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_2025() {
65    }
66}
67