解题思路

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

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

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

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

  因为任意非整段子段要么不含第一个元素，要么不含最后一个元素（或两者都不含），因此必出现在上述两段之一中。

• 用 Kadane 算法分别在两段上求最大子段和，若结果 $\ge S$，输出 Yes，否则 No。

• 时间复杂度：每组 $O(n)$；空间复杂度：$O(1)$。

复杂度

• 时间：$O(n)$ 每组
• 空间：$O(1)$

代码实现

Python

import sys

def kadane(a, l, r):
	# 计算 a[l..r] 的最大子段和（l、r 为闭区间）
	cur = -10**18
	best = -10**18
	for i in range(l, r + 1):
		if cur < 0:
			cur = a[i]
		else:
			cur += a[i]
		if cur > best:
			best = cur
	return best

def main():
	data = list(map(int, sys.stdin.read().strip().split()))
	t = data[0]
	idx = 1
	out = []
	for _ in range(t):
		n = data[idx]; idx += 1
		a = data[idx:idx+n]; idx += n
		S = sum(a)
		# 前 n-1 段与后 n-1 段上的最大子段和
		left = kadane(a, 0, n - 2)
		right = kadane(a, 1, n - 1)
		out.append("Yes" if max(left, right) >= S else "No")
	print("\n".join(out))

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static long kadane(int[] a, int l, int r) {
		// 计算 a[l..r] 的最大子段和
		long cur = Long.MIN_VALUE / 4;
		long best = Long.MIN_VALUE / 4;
		for (int i = l; i <= r; i++) {
			if (cur < 0) cur = a[i];
			else cur += a[i];
			if (cur > best) best = cur;
		}
		return best;
	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		while (T-- > 0) {
			int n = sc.nextInt();
			int[] a = new int[n];
			long S = 0;
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				S += a[i];
			}
			long left = kadane(a, 0, n - 2);
			long right = kadane(a, 1, n - 1);
			sb.append(Math.max(left, right) >= S ? "Yes" : "No").append('\n');
		}
		System.out.print(sb.toString());
	}
}

C++

#include <bits/stdc++.h>
using namespace std;

long long kadane(const vector<long long>& a, int l, int r) {
	// 计算 a[l..r] 的最大子段和
	long long cur = LLONG_MIN / 4, best = LLONG_MIN / 4;
	for (int i = l; i <= r; ++i) {
		if (cur < 0) cur = a[i];
		else cur += a[i];
		best = max(best, cur);
	}
	return best;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T; 
	if (!(cin >> T)) return 0;
	while (T--) {
		int n; cin >> n;
		vector<long long> a(n);
		long long S = 0;
		for (int i = 0; i < n; ++i) { cin >> a[i]; S += a[i]; }
		long long left = kadane(a, 0, n - 2);
		long long right = kadane(a, 1, n - 1);
		cout << (max(left, right) >= S ? "Yes" : "No") << '\n';
	}
	return 0;
}

题目内容

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

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

输入描述

第一行一个正整数 $T$ ，表示有 $T$ 组数据。

对于每一组数据，第一行一个正整数 $n$ ; 第二行 $n$ 个数 $a_1,a_2,...,a_n$ 。

$3≤n≤5*10^4,-100≤a_i≤100,1≤T≤5$

输出描述

对于每一组数型，如果找得到这样的 $l,r$ ，输出 $Yes$ ; 否则，输出 $No$ 。

样例1

输入

2
4
1 2 3 4
3
-5 5 -5

输出

No
Yes

说明

第一组数据，无论 $l,r$ 如何选择都比全选的美味度之和要小;

第二组数据，可以选择 $[l,r]=[1,1]$ ，美味度之和为 $-5$ ，等于全部选择的美味度之和。

当然也可以选择 $[l,r]=[1,2]$ ，美味度之和为 $0$ ，大于全部选择的美味度之和。