#2025
Maximum Number of Ways to Partition an Array
master · 1835 · lc hard +32 · verified · 35.6% accepted · 520 likes · top 13%
Description
Given a 0-indexed integer array nums and an integer k, you may optionally replace exactly one element of nums with k (or leave the array as-is). A valid partition exists at index pivot (where 1 <= pivot < n) when the prefix sum equals the suffix sum. Return the maximum number of valid partition indices achievable.
Example 1:
Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.
Example 2:
Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.
Example 3:
Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.
Code
1
2
3