Maximum Number of Ways to Partition an Array
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:
1 <= pivot < nnums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
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.
Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.
Example 1
Input
nums = [2,-1,2], k = 3Output
1One optimal approach is to change nums[0] to k, making the array [3, -1, 2], which has one valid partition at pivot = 2.
Example 2
Input
nums = [0,0,0], k = 1Output
2The optimal approach is to leave the array unchanged, which gives valid partitions at pivot = 1 and pivot = 2.
Constraints
- n == nums.length
- 2 <= n <= 10^5
- -10^5 <= k, nums[i] <= 10^5