====== 연속합 ======

===== 풀이 =====
  * [[ps:최대 부분합]] 문제. Kadane algorithm을 사용해서 O(n)에 해결가능.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1912. 연속합".

- Problem link: https://www.acmicpc.net/problem/1912
- Solution link: http://www.teferi.net/ps/problems/boj/1912

Tags: [DP]
"""

INF = float('inf')


def maximum_subarray(nums):
    max_sum, cur_sum = -INF, 0
    for num in nums:
        cur_sum = max(num, cur_sum + num)
        max_sum = max(max_sum, cur_sum)
    return max_sum


def main():
    n = int(input())  # pylint: disable=unused-variable
    nums = [int(x) for x in input().split()]

    print(maximum_subarray(nums))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_2}}