문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

코드

n = int(input())
arr = list(map(int, input().split()))

res = max(arr)
if res <= 0:
	print(res)
else:
	
	mx = 0
	t = 0
	for i in range(n):
		if t + arr[i] > 0:
			t += arr[i]
		else:
			t = 0
		
		mx = max(mx, t)
	
	print(mx)

설명

개수에는 상관없이 연속된 합이 최대인 값을 찾아내는 것이기 때문에 0번 인덱스부터 끝까지 합하는데 누적된 합과 더해지는 숫자의 합이 0이 아닌 경우 계속해서 합을 해가고 누적 합 중 최대인 경우를 저장한다. 만약 누적 합이 음수로 변한 경우 0으로 초기화 해준다.