[파이썬/python] 백준 - 1912 연속합

문제

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

---

문제 설명

1.   N개의 정수로 이루어진 임의의 수열이 주어진다.
2. 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.
   1. 단 수는 1개 이상 선택한다.

 

---

풀이

두 개의 반복문을 이용해서 현재 위치기준 이전 값들을 더해가며 최댓값을 갱신하면 답을 구할 수 있다.

하지만 이 방법은 $N^2$의 시간복잡도를 요구하기 때문에 $N = 10^5$인 이 문제에서는 적합하지 않다.

 

따라서 $O(N)$으로 해결할 수 있는 방법을 생각했다.

 

이 문제에서는 연속된 수를 선택한다는 것이 핵심이다.

내가 현재 특정 원소에 있을 때 선택할 수 있는 경우는 두 가지이다.

 

1. 이전에 연속된 수에서 최댓값이 나올 수 있을 때 이전 + 현재 원소를 선택한다.

2. 이전의 연속된 수의 합이 현재 원소보다 작을 때 현재 원소를 선택한다.

이를 통해서 현재 원소에서 선택할 수 있는 최댓값을 구했다.

 

점화식으로 표현해보면

dp [현재의 값] = max(dp[이전의 값] + arr[현재의 값], arr[현재의 값])

dp [i] = max(dp[i-1] + arr[i], arr[i])으로 나타낼 수 있다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))

dp = [0 for _ in range(n)]

dp[0] = arr[0]

for i in range(1,n):
    dp[i] = max(dp[i-1]+arr[i], arr[i])

print(max(dp))

---

시간복잡도

• 1차원 반복문을 통한 다이나믹 프로그래밍이므로 $O(N) = O(10^5)$의 시간복잡도가 소요된다.