[PS]BOJ1912 연속합 ( dp ) With 파이썬

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

◎ 문제풀이 

 

n까지의 정수 중 최대의 연속된 합을 구하는 문제이다. 

n까지의 정수 중에 연속된 최대의 합은 두 가지 경우가 있다. 

 

1) 연속된 합이 n까지 연속되는 경우

2) 연속된 합이 n까지 연속되지 않은 경우

 

2가지 경우 중 최대값을 구하면 된다. 

 

◎ 코드 

#BOJ1912 연속합 (dp)

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
dp = [ [0,0] for _ in range(n) ]

dp[0][0] = arr[0] # n자리의 최댓값
dp[0][1] = arr[0] # n까지 연속된 경우의 최댓값

for i in range(1,n) :
  tmp = dp[i-1][1] + arr[i] 
  dp[i][1] = arr[i] if arr[i] > tmp else tmp 
  dp[i][0] = max(dp[i-1][0],dp[i][1]) #두 가지 경우 중 최댓값 구하기
    
print(dp[n-1][0])