[백준-13398] 연속합 2

코드

import sys
input = sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))

dp=[[0]*n for _ in range(2)]
dp[0][0]=a[0]

if n>1:
    result=-sys.maxsize
    for i in range(1,n):
        dp[0][i]=max(dp[0][i-1]+a[i],a[i])
        dp[1][i]=max(dp[1][i-1]+a[i],dp[0][i-1])
        result=max(result,dp[0][i],dp[1][i])
    print(dp)
    print(result)
else:
    print(dp[0][0])

수행시간: 208ms

풀이

생각해보다가 풀리지 않아 검색을 통해서 풀었다.
dp[0][i]는 특정 원소를 제거하지 않은 경우
dp[1][i]는 특정 원소를 제거한 경우
어떠한 원소도 삭제하지않는 경우는 (이전까지의 연속합+i번째원소)와 (i번째 원소)중 큰값을 대입
어떠한 원소를 삭제한 경우는 2가지로 나누어 생각한다.
1. i번째 원소를 삭제한 경우
2. i 이전 원소를 삭제한 경우
1번은 dp[0][i-1] 이다.
2번은 dp[1][i-1]+a[i] 이다.
1번과 2번중 큰값을 대입한다.
반복이 끝나면 최대값을 출력한다.
이때 print(max(max(dp[0]),max(dp[1]))로 최대값을 찾으면 만약 원소들이 모두 음수일 경우 dp[1][0]같인 0을 최대값으로 찾게되어 오답이 나온다.
그리고 n=1일경우엔 무조건 1개원소를 선택해야하므로 1개원소를 출력한다.