테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Equator ======

===== 풀이 =====
  * [[ps:최대 부분합]]을 구하는 문제. 다만 주어진 배열이 원형으로 되어있기 때문에, 부분구간이 두개로 나뉘어져 왼쪽끝과 오른쪽끝에 붙어있는 경우도 고려해야 한다.
  * 원형 배열에서 부분구간을 찾을때 흔히 쓰는 테크닉은 배열을 두번 이어붙인 다음에 찾는 것이지만, 여기에는 바로 적용할수는 없고, 굳이 쓰려면 좀더 로직을 추가해야 하는데 그것보다 더 간단한 방법이 있다.
  * 최대 부분합과 최소 부분합을 모두 찾은 다음에, 최대부분합과 전체합-최소부분합 중에서 큰 값을 택하는 것이다. 최대부분합은 구간이 하나로 되어있을때의 최댓값, 전체합-최소부분합은 구간이 두개로 나눠져있을때의 최댓값에 대응된다.
  * 시간복잡도는 O(n)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 10274. Equator".

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

Tags: [dp]
"""

INF = float('inf')


def maximum_subarray(nums):
    max_sum, cur_max_sum = -INF, 0
    min_sum, cur_min_sum = INF, 0
    for num in nums:
        cur_max_sum = max(num, cur_max_sum + num)
        max_sum = max(max_sum, cur_max_sum)
        cur_min_sum = min(num, cur_min_sum + num)
        min_sum = min(min_sum, cur_min_sum)

    return max(0, max_sum), min(0, min_sum)


def main():
    T = int(input())
    for _ in range(T):
        _, *c = [int(x) for x in input().split()]
        max_sum, min_sum = maximum_subarray(c)
        print(max(max_sum, sum(c) - min_sum))


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

{{tag>BOJ ps:problems:boj:골드_5}}