[백준] 1912번 : 연속합 (Python)

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

 

n개의 정수로 이루어진 임의의 수열이 주어졌을 때,

이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제다.

import sys

input = sys.stdin.readline

N = int(input())
card = list(map(int, input().split())) # 수열 입력받기

# DP 테이블 생성
for i in range(1, N):
    card[i] = max(card[i], card[i]+card[i-1]) # 구간합, 수열의 값 중 큰 값 저장

print(max(card)) # 최댓값 출력

 

 

[문제풀이]

---

 

이 문제는 동적 계획법, 즉 DP를 이용해서 풀 수 있다.

 

 

 

수열 처음부터 구간합을 구한다.

단, 이때 해당 구간합보다 수열의 값이 큰 경우, 수열의 값으로 설정!

 

 

이렇게 구해낸 구간 합 중 제일 큰 값이 전 구간에서의 구간합의 제일 큰 값이다!