编程题
### 问题描述 小郑现在得到了串长度为 $N$ 的数列 $A$,小张非常聪明,她立即声称这个数列的最大的连续子序列的和为 $X$ (不保证其正确性)。 小郑很狡猾,他偷偷摸摸得修改了数列 $A$ 中的一个数字,使之正负号翻转(即从 $X$ 变为 $-X$),并且说:你错了,最大子段和明明是 $Y$。 现在你的任务是找出一个翻转方法,使得翻转后存在一个连续子序列的和大于 $X$。 注意,如果数列完全由非正数组成,那么其最大连续子序列的和为 $0$。 最大连续子序列的和又称最大子段和,其长度可为 $0$,故最大子段和最小值为 $0$。 ### 输入格式 第一行包含两个数字 $N$ 和 $X$。 之后一行 $N$ 个数字代表数列 $A_i$。 ### 输出格式 小郑在输入的数列 $A$ 中,翻转一个数字(取负数,即从 $X$ 变为 $-X$)后,如果存在一个连续子序列的和大于 $X$,则输出 `YES`,否则输出 `NO`。 ### 样例输入 1 ```text 5 5 1 -2 3 -4 5 ``` ### 样例输出 1 ```text YES ``` ### 样例输入 2 ```text 5 5 1 -2 3 -4 5 ``` ### 样例输出 2 ```text NO ``` ### 样例说明 在样例 $1$ 中,小郑可以将 $-4$ 翻转至 $4$,现在的最大子段和为 $3+4+5$。 注意,小郑必须翻转一个数字。 ### 评测数据规模 对于所有评测数据,$0 \lt N \lt 500,0 \le X \lt 10^{15},-10^5 \lt a_i \lt 10^5$。
查看答案
赣ICP备20007335号-2