[python3] 1912번 연속합

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

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

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

Kadane's algorithm

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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))