又一最大子段和
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

大家好,今天我们来聊聊最大子段和是怎么回事呢?最大子段和相信大家都很熟悉,但是最大子段和又是怎么回事呢?下面就让小编带大家一起了解吧。 最大子段和,其实就是最大子段和了。大家可能会感到很惊讶,最大子段和怎么......

我们将一个数列的最大子段和的值记为,现在你可以对进行若干次操作,每次操作,你可以选择数列中的一个数字,将其改为之间的任意一个数。现在,给定整数,求最少需要操作多少次可以使得

最大子段和是指选出数列中连续且非空的一段使得这段的和最大。

输入描述:

输入第一行是一个整数,测试用例数。

每个测试用例的第一行包括两个数,表示数组的长度和需要达到的

每个测试用例的第二行输入n个数字,数组的个元素。

输入保证对于所有测试用例,有

输出描述:

对于每个测试用例,输出一行一个整数,表示令最少所需的操作次数。
示例1

输入

复制
4
3 0
-1 -1 -1
3 -1
-1 -1 -1
3 -2
-1 -1 -1
7 3
2 -4 3 -1 2 -4 3

输出

复制
1
0
3
1