테페리넷

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

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

===== 풀이 =====
  * [[ps:problems:boj:1912]] 문제에서, 수 한개를 제거할수 있다는 조건이 추가된 문제이다.
  * [[ps:최대 부분합]]을 푸는 Kadane algorithm을 살짝 변형해서 적용하면 된다. 수를 제거하지 않았을때의 i에서 끝나는 최대 부분합과 수를 1개 제거했을 때의 i에서 끝나는 최대 부분합 두가지를 dp로 갱신해가면 된다. tl간복잡도는 O(n)

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

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

Tags: [DP]
"""

INF = float('inf')


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

    sum_with_del = sum_without_del = answer = -INF
    for num in nums:
        sum_with_del = max(sum_without_del, num + sum_with_del)
        sum_without_del = max(num, num + sum_without_del)
        answer = max(answer, sum_with_del, sum_without_del)

    print(answer)


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

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