연속합 2 풀이

문제 링크: https://www.acmicpc.net/problem/13398

백준 알고리즘 기초 1/2 401에서 11번째 - 13398번 연속합 2를 풀어보았다.

 

풀이: dp를 2개로 나눠서 푸는 문제였다. 코드는 https://ji-gwang.tistory.com/289 를 참고했다.

 

C++

 

Python

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

Java