이번 문제는 다이나믹 프로그래밍을 응용하여 해결하였다. 처음에는 하나의 수를 제거할 수 있다는 점에서 단순하게 cnt라는 변수를 0으로 두고, dp[i]>dp[i]+arr[i+1]일 때 cnt를 1 증가시켜 하나의 수를 제거한 것으로 처리를 하였다. 의도한 내용은 잘 작동하였지만 주어진 예제 10, -4, 3, 1, 5, 6, -35, 12, 21, -1에서 3, 1, 5, 6, 12, 21의 합이 결과로 도출되었다. 이를 두고 생각해보니 10에서 -4로 넘어갈 때 cnt가 증가하였기 때문에 -35에서 끝나버리게 되고, 3에서 시작하면 -35를 빼고 21까지 더해지는 결과가 나온다는 것을 깨달았다. 고민 끝에 dp를 2차원 배열로 하여 처리하기로 하였다.

• n을 입력받는다.
• 임의의 수열 arr을 입력받는다.
• 다이나믹 프로그래밍을 위한 배열 dp를 2차원으로 하여 n만큼 할당한다. dp[x][0]은 수를 제거하지 않은 상태에서의 합이고, dp[x][1]은 수를 제거한 상태에서의 합을 의미한다.
• dp[0][0]에는 arr의 첫번째 수를, dp[0][1]에는 임의의 매우 작은 수를 입력한다.
• arr에 음수만 들어갈 수 있기 때문에 answer은 임의의 매우 작은 수로 정의한다.
• 1부터 n까지의 for문을 돌린다.
  -> dp[i][0]에는 dp[i-1][0]+arr[i]와 arr[i] 중 더 큰값으로 갱신한다.
  -> dp[i][1]에는 dp[i-1][0]과 dp[i-1][1]+arr[i] 중 더 큰 값으로 갱신한다.
• 0부터 n까지의 for문을 돌린다.
  -> answer에 내장함수 max를 사용하여 answer과 dp[i] 중 더 큰 값으로 갱신한다.
• answer를 출력한다.

Code

n=int(input())
arr=list(map(int, input().split()))
dp= [[0, 0] for i in range(n)]
dp[0]=[arr[0], -999999999]
answer=-999999999
for i in range(1, n):
    dp[i][0]=max(dp[i-1][0]+arr[i], arr[i])
    dp[i][1]=max(dp[i-1][0], dp[i-1][1]+arr[i])
for i in range(n):
    answer=max(answer, max(dp[i]))
print(answer)