[백준_1912]_연속합_python

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

1912번: 연속합

문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

문제해결

다이내믹 프로그래밍 문제이다. n의 범위가 100000까지 주어지기 때문에 O(N^2)인 방법으로 풀지 못하고 dp배열에 값을 저장시켜 O(N)으로 푸는 방법을 생각해야 한다.  

dp(i)를 정의하자면 i가 끝점이라 하였을 때의 최댓값을 작은 것부터 처리하여 dp배열에 저장하는 것이다.

 1. 선택한 연속 부분 수열의 마지막 위치와 2. 연속 부분 수열 내 원소의 합이 같기에 위 그림의 두 가지 경우는 동일한 상황이다.

dp배열에는 i지점(끝점)에서의 최댓값을 저장한다.

점화식은 dp [i] = max(dp [i-1]+arr [i], arr [i]),

초기값은 dp [0] = arr [0]으로 설정한다.

1~5까지의 최댓값을 dp배열에 저장하여 그중 최댓값을 구하면 된다.

 

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
dp = [0]*n      #dp배열의 값은 해당위치에 있을때의 최댓값이다.
dp[0] = arr[0]  #초기값설정
for i in range(1,n):
    dp[i]=max(dp[i-1]+arr[i],arr[i])
print(dp)
print(max(dp))