링크:https://www.acmicpc.net/problem/28433
길이 N인 수열에서 구간 합이 양수인 구간의 개수가 음수인 구간의 개수를 초과하도록 구간을 나누는 문제
수열 A를 순회하며 a[i]가 음수인지 양수인지 확인하며 아래의 조건을 실행
a[i]가 양수고 이전 구간 확인
1. 양수구간
문제에서는 구간을 구하는 문제라서 이전 구간의 양수가 얼마나 크던
구간을 나누어 개수를 늘려준다
2.음수 구간
이전 구간에 a[i]를 더해서 0보다 커질경우 음수구간개수를 -1 해주고 양수구간 개수를 +1 해주어
이전 음수구간을 양수 구간으로 바꿔준다
만약 이전 구간에 a[i]를 더해도 0보다 작을경우는 구간에 포함시키지 않고 새로운 양수 구간을 만들어준다
a[i]가 음수고 이전 구간 확인
1. 음수 구간
양수 구간과는 반대로 음수 구간은 최대한 합쳐주는 게 좋으니까 이전 구간 합이 음수일 경우는
구간을 나누지 않고 계속 합쳐준다
2. 양수 구간
이전 구간이 양수고 음수인 a[i]를 더해도 구간이 양수일 때에는 양수 구간에 a[i]를 포함해 주어
음수 구간으로 나누지 않는다
만약 a[i]를 더했을 때 구간 합이 0보다 작아진다면 이전 양수 구간에 포함하지 않고 새로운 음수 구간을 만들어 준다.
import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
m = int(input())
lst = list(map(int,input().split()))
sumCount = 0 # 구간 카운트
ans = 0
currentSum = 0
for x in lst:
if x > 0: #양수
if currentSum >= 0:
sumCount +=1
currentSum = x
elif currentSum < 0:
if currentSum + x > 0:
sumCount +=2
currentSum += x
else:
currentSum = x
sumCount +=1
if x < 0: #음수
if currentSum >= 0:
if currentSum + x > 0:
currentSum += x
else:
sumCount -=1
currentSum = x
elif currentSum < 0:
currentSum += x
if sumCount > 0:
print('YES')
else:
print('NO')