[python3] 1912번 연속합

처음에는 brute force 방법을 사용해서 문제를 풀어보려 하였다.

하지만 시간 초과가 생겨 다른 방법을 찾아야 했다.

그러던 중 위키피디아에서 이 알고리즘을 찾게 되었다.

Kadane's algorithm

n = int(input())
sequencestr = input().split()
sequence = list(range(n))

for repeat in range(0, n):
	sequence[repeat] = int(sequencestr[repeat])

class cs:
	def msa(self, num, n):
		sm = num[0]
		result = num[0]

		for repeat in range(1, n):
			sm = max(sm + num[repeat], num[repeat])
			result = max(sm, result)

		return result

mx = cs()
print(mx.msa(sequence, n))