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

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

1912번: 연속합

Problem

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

조건

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

SOL

완전탐색으로 푼다면, N^2이 나오게 되는건 어렵지 않게 떠올릴 수 있다. (for i in range(n) : for j in range(i,n): 꼴)

그렇다면, N^2 = 10^10 이기때문에, 시간초과가 날거임.

 

따라서, 반복문을 1개 사용해서 이 문제를 해결해야한다. 즉, DP문제임.

최댓값을 어떻게 구할 수 있을까 생각해보면, 더하기 라는건 , 더하는 숫자가 음수가 아닌 이상 ,더하는게 좋다.

 

하지만, 연속된 숫자를 더하는 과정이기 때문에, 더하는 숫자가 음수여서, 더하지 않으면, 연속성이 끊기게 된다.

예를들어, A=[100,2,3,-1,500000,1] 이라는 배열이 있다면, 끊기지 않고, 모든 숫자를 다 더하는게 가장 큰 값이다. 

 

그래서,이때 까지 더한 값과, 현재 더할 수를 비교해서, 기록하는 방식으로 구현하기로 했다.

왜냐하면, 연속된 합들의 값들은, 우리가 구하는 가장 큰 합을 구하기 위해서 필요한 정보이고, 그걸 현재 더할 수랑 비교하는건, 시작점을 어디로 할지 계속 비교해주는 과정이다. 그래서, 답은 max(DP)일거임.

이러면 O(2N)에 가능해질거다.

 

• 정의:DP[n] = n번째 까지, 연속된 합들의 값들을 저장해 놓은 배열 
• 초기값:DP[0] = arr[0]
• 점화식:DP[N] = max(arr[i],DP[i-1]+arr[i])
• 답:max(DP)

N = int(input())
arr=list(map(int,input().split()))
#print(arr)
DP=[0]*N
DP[0] =arr[0]

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

#print(DP)
print(max(DP))