문제풀이/DP

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

IT록흐 2023. 7. 4. 10:00
반응형

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

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

◎ 문제풀이 

 

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])

 

반응형