[백준] 13398- 연속합2

• 기존 연속합 문제에서 숫자를 빼거나 안빼거나의 조건이 추가된 문제이다.

• 어려워서 풀이를 보며 풀었다... DP 너무 어렵다..

➡️ 기존 연속합 문제에서는 1차원 dp배열로 해결이 되었지만 숫자 제거 여부가 있기 때문에 2차원 dp 배열이 필요하다.

따라서

1. dp[i][0]은 i까지 오면서 숫자를 뺀 적이 없는 경우
2. dp[i][1]은 i까지 오면서 숫자를 뺀 적이 있는 경우

1번의 경우를 생각해보면 i-1까지 숫자를 뺀 적이 없는 값과 현재값을 비교해줘야 한다.

즉 dp[i][0] = max(dp[i-1][0]+number[i], number[i]) 이다.

여기서 기본적인 누적합, 디피 설명을 하자면 지금까지 추가해 온 값과 현재값을 더했을 때 현재값보다 작다면 지금까지 연산한 것을 버리는 개념이다.

2번의 경우는 자기 자신을 지금 빼거나, 이미 뺀 적인 있는 dp값에 현재값을 더한 것을 비교해주면 된다.

dp[i][1] = max(dp[i-1][0], dp[i-1][1]+number[i])

n = int(input())

number = list(map(int, input().split()))


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


dp[0][0] = number[0]


answer = -1e10


for i in range(1, n):
    
    dp[i][0] = max(dp[i-1][0]+number[i], number[i])


    dp[i][1] = max(dp[i-1][0], dp[i-1][1]+number[i])

    answer= max(answer, max(dp[i][0], dp[i][1]))
    
if answer == -1e10:
    print(dp[0][0])
else:
    print(answer)