3511. 构造正数组 🔒

English Version

题目描述

给定一个数组 nums。一个数组被认为是 正 的，如果每个包含 超过两个 元素的 子数组 的所有数字之和都是正数。

您可以执行以下操作任意多次：

• 用 -10¹⁸ 和 10¹⁸ 之间的任意整数替换 nums 中的 一个 元素。

找到使 nums 变为正数组所需的最小操作数。

 

示例 1：

输入：nums = [-10,15,-12]

输出：1

解释：

唯一有超过 2 个元素的子数组是这个数组本身。所有元素的和是 (-10) + 15 + (-12) = -7。通过将 nums[0] 替换为 0，新的和变为 0 + 15 + (-12) = 3。因此，现在数组是正的。

示例 2：

输入：nums = [-1,-2,3,-1,2,6]

输出：1

解释：

具有 2 个以上元素且和非正的子数组是：

子数组下标	子数组	和	替换后的子数组（令 nums[1] = 1）	新的和
nums[0...2]	[-1, -2, 3]	0	[-1, 1, 3]	3
nums[0...3]	[-1, -2, 3, -1]	-1	[-1, 1, 3, -1]	2
nums[1...3]	[-2, 3, -1]	0	[1, 3, -1]	3

因此，nums 在一次操作后是正的。

示例 3：

输入：nums = [1,2,3]

输出：0

解释：

数组已经是正的，所以不需要操作。

 

提示：

• 3 <= nums.length <= 105
• -109 <= nums[i] <= 109

解法

方法一

Python3

class Solution:
    def makeArrayPositive(self, nums: List[int]) -> int:
        l = -1
        ans = pre_mx = s = 0
        for r, x in enumerate(nums):
            s += x
            if r - l > 2 and s <= pre_mx:
                ans += 1
                l = r
                pre_mx = s = 0
            elif r - l >= 2:
                pre_mx = max(pre_mx, s - x - nums[r - 1])
        return ans

Java

class Solution {
    public int makeArrayPositive(int[] nums) {
        int ans = 0;
        long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.length; r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = Math.max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int makeArrayPositive(vector<int>& nums) {
        int ans = 0;
        long long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.size(); r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
};

Go

func makeArrayPositive(nums []int) (ans int) {
	l := -1
	preMx := 0
	s := 0
	for r, x := range nums {
		s += x
		if r-l > 2 && s <= preMx {
			ans++
			l = r
			preMx = 0
			s = 0
		} else if r-l >= 2 {
			preMx = max(preMx, s-x-nums[r-1])
		}
	}
	return
}

TypeScript

function makeArrayPositive(nums: number[]): number {
    let l = -1;
    let [ans, preMx, s] = [0, 0, 0];
    for (let r = 0; r < nums.length; r++) {
        const x = nums[r];
        s += x;
        if (r - l > 2 && s <= preMx) {
            ans++;
            l = r;
            preMx = 0;
            s = 0;
        } else if (r - l >= 2) {
            preMx = Math.max(preMx, s - x - nums[r - 1]);
        }
    }
    return ans;
}