2025. Maximum number of ways to split an array

This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

2025. Maximum number of ways to split an array

You are given an array of integers with subscripts starting at 0 and length N nums. The number of schemes for dividing the array NUMs is defined as the number of pivot points that meet the following two conditions:

1 <= pivot < n
nums[0] + nums[1] + … + nums[pivot – 1] == nums[pivot] + nums[pivot + 1] + … + nums[n -1]

And I give you an integer k. You can change an element in numS to k or leave the array unchanged.

Return the maximum number of ways to split NUMS so that both conditions are met without changing at most one element.

Example 1: Input: nums = [2,-1,2], k = 3 Output: 1 Explanation: An optimal scenario would be to change nums[0] to k. The array becomes [3,-1,2]. There is a way split array: - the pivot = 2, we have divided | 2] [3-1:3 + 1 = = 2. Example 2: input: nums = [0,0,0], k = 1 output: 2 explanation: an optimal scenario is to leave the array untouched. There are two ways to partition the array: - the pivot = 1, we have divided | 0, 0 0:0 = = 0 + 0. - the pivot = 2, we have divided [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: an optimal solution would be to change nums[2] to k. Array into [22, 4-33-20, 15, 15, 16 -,7,19, -, 0, 10-13, and 14]. There are four ways to split an array.Copy the code

Tip:

n == nums.length
2 <= n <= $10^5$
−105-10^5−105 <= K, NUMs [I] <= 10510^5105

Their thinking

For nums[0] + NUMs [1] +… + nums[pivot – 1] == nums[pivot] + nums[pivot + 1] + … + nums[n – 1]

We add nums[0] + nums[1] +… + nums[pivot – 1] + nums[pivot – 1] + nums[pivot – 1] + nums[pivot – 1] +… + nums[n-1] is called back, and the sum of the entire array is sum.

Maintains an array of prefixes and pre

Sum [I]*2=sum is a delimiter when the array is not changed
When changing an element of an array, we iterate through all the elements, trying to change them, and maintain two maps that represent prefixes and sums that precede and follow the current element. It can be found that when we try to change the elements, it does not affect the preceding prefix sum, but causes the following prefix sum to change D (d is the difference between the target element k and the original element). Therefore, for the prefix sum that meets the preceding conditions, the calculation formula is sum[I]=sum+d-sum[I], and for the following prefix sum, the calculation formula is sum[I]+d=sum+ D -(sum[I]+d).

code


class Solution {
public:
    int waysToPartition(vector<int> nums, int k) {

        int res(0).n(nums.size());

        vector<long long> pre(n + 1);
        map<long long.int> ml;
        map<long long.int> mr;
        for (int i = 0; i < n; ++i) {
            pre[i + 1] = pre[i] + nums[i];
            if(i+1<n)
            mr[pre[i+1]] + +; }long long sum = pre[n];
        if (sum%2= =0)
            res=mr[sum/2];
        for (int i = 1; i <= n; ++i) {
            long long d=k-nums[i- 1],new_sum=sum+d;
            if (new_sum%2= =0){
                res=max(res,ml[new_sum/2]+mr[new_sum/2-d]);
            }
            ml[pre[i]]++;
            mr[pre[i]]--;
        }
        returnres; }};Copy the code

2025. Maximum number of ways to split an array