解题思路

• 设总和为 $S=\sum_{i=1}^n a_i$。

• 需要判断是否存在“非整段”的连续子段，其和 $\ge S$。

• 关键结论：所有“非整段”的连续子段的最大子段和，等于

  • 在前 $n-1$ 个元素上的最大子段和，和
  • 在后 $n-1$ 个元素上的最大子段和 的最大值。即

题目内容

某片场需要给参演人员采购盒饭，负责后勤的小周来到食堂，食堂里一共有 $n$ 种不同的盒饭，种类标记为 $1,2,3,...,n$ ，每种盒饭都有一个美味度 $a_i$ 。$a_i$ 越大，表示盒饭越好吃，由于有些盒饭味道可能很奇怪，于是 $a_i$ 有可能小于等于 $0$ 。

小周不了解演员们的口味偏好，于是每种盒饭都买了一份。回片场的路上小周在想：能不能找到这样一对 $l,r$ 满足 $1≤l≤r≤n$ ，且不满足 $[l,r]=[1,n]$ (即全选)，使得将 $[l,r]$ 这个种类内的盒饭各要一份，其美味度之和大于等于每一种会饭都买一份的美味度之和?

输入描述