연속합 2

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

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