https://www.acmicpc.net/problem/13398
13398번: 연속합 2첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net
도저히 나의 편협한 사고방식으로는 이해되지 않아
힌트를 얻었다. 생각보다 간단하다.
먼져,수열 a를 받는다.
그후, 2차원 dp배열을 생성한다.
dp[i][0]은 i를 포함하는 수열 중 가장 큰 수열의 합이다.
dp[i][1]은 i를 포함하는 수열에서 하나를 뺐을 때 가장 큰 수열의 합이다.
dp[i][0]은 그냥 그 전의값이 0보다 클 때만 더하고, 아니면 a[i]를 반환하면 된다.
dp[i][0]= max(dp[i-1].0)+a[i]
dp[i][1]은 그 전의값+a[i]와, 아무것도안뺐을때의값(dp[i-1][0] 즉, i를 제외했을 경우)
중 큰 수를 반환하면 된다.
dp[i][1]=max(dp[i-1][1]+a[i] , dp[i-1][0] )
이와 같은 점화식이 나온다.
마지막에 계속 틀렸습니다가 나와서 봤더니, 수열에서 수를 무조건 하나이상 선택해야 한단다.
그런데, 모든 경우에서 수를 하나 이상 선택하지만, a[0]이 음수일때
dp[0][1]은 수를 선택하지 않으므로 0이 된다.
이를 방지하기 위해 모든 반복이 끝난후 dp[0][1]을 a[1]로 업데이트시켜줬더니 풀렸다.
코드
n=int(input())a=[*map (int,input().split())] #수열
dp=[[0,0] for _ in range(len(a))] #[0]은 아무것도안뺏을때, [1]은 뭐하나뺐을때dp[0][0]=a[0]
for i in range(1,len(dp)): if dp[i-1][0]>=0: dp[i][0]=dp[i-1][0]+a[i]
else: dp[i][0]=a[i] dp[i][1]=max(dp[i-1][1]+a[i],dp[i-1][0])
dp[0][1]=a[0] #맨 처음에 하나이상 선택해야 하므로 조정answer=max([max(x) for x in dp])
print(answer)