문제

입력 , 출력

Solution

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
res = [[0] * n for _ in range(2)]
maxres = arr[0]
if n == 1:
    print(arr[0])
else:
    res[0][0] = arr[0]
    for i in range(1, n):
        res[0][i] = max(res[0][i - 1] + arr[i], arr[i])
        res[1][i] = max(res[1][i - 1] + arr[i], res[0][i - 1])
        maxres = max(maxres, res[0][i], res[1][i])
    print(maxres)

설명

res[1][i] 에는 i번째를 선택하지 않거나 전에 뺀것중에서 최대값 res[1][i-1] 에서 arr[i] 를 더한것 중에 최대값을 넣게된다.

후기

이해하는데 엄청 오래걸렸다..
나는 빡빡이다