해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 1912 연속합 - dp

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

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

풀이

1. DP 문제입니다.

2. DP의 i-1번째의 값이 0보다 크면, DP[i] = DP[i-1] + Arrar[i] 해줍니다.

3. DP의 i-1번째의 값이 0보다 작으면, DP[i]에는 배열의 i의 값을 넣어줍니다.

=> DP[i] = Arrar[i]

4. DP 리스트의 값중 가중 큰 값을 출력합니다.

전체 코드

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

INF = -float("inf")
dp = [INF] * 100002
dp[0] = a[0]

for i in range(1, n):
    if dp[i-1] > 0:
        dp[i] = dp[i-1] + a[i]
    else:
        dp[i] = a[i]

print(max(dp))