1912번: 연속합

1912번: 연속합

 

DP문제다.

n개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제

시간 제한은 1초고 n의 범위가 10만이하이므로 O(NlogN)까지는 가능하겠다는 생각을 했다.

 

먼저 문제를 풀 때, DP는 점화식을 만들어야 하므로 현재 항과 이전 항의 관계를 구하려고 했다.

 

예를 들어

10 -4 3 1 5 6 -35 12 21 -1

이라는 수열이 있을 때, 

 

5가 포함된 연속합 중 최댓값을 구하려면 

1. 10 + (-4) + 3 + 1 + 5

2. -4 + 3 + 1 + 5

3. 3 + 1 + 5

4. 1 + 5

5. 5

중 최댓값을 구하면 된다.

 

여기서 1~4번은 5 이전 수인 1까지의 최댓값에 5를 더한 것과 동일하므로

1~4번의 최댓값 -> dp[n-1] + n

5번 -> n

이 둘의 최댓값, 즉, max(dp[n-1] + n, n)을 구하면 된다.

 

n번째 수가 포함된 연속합 중 최댓값 = max(dp[n-1] + n, n)

 

처음에는 dp테이블에 해당 n번째 수까지의 전체 연속합 중 최댓값을 구하는 줄 알고, n번째 수가 연속합에 포함되지 않는 경우도 따로 구해야되나 생각했는데 그럴 경우 n번째 수가 연속합에 포함되지 않는다면 그 다음 dp값부터 정해줄 방법이 엄청 복잡해진다.

왜냐하면 만약 n번째 값이 연속합 중 최댓값에 포함되지 않는다고 해도, 뒤에 dp값을 갱신하다보면 n번째 값이 포함된 연속합이 최댓값이 될 수도 있기 때문이다.

 

그래서 앞서 위에서 구한 n번째 수가 포함된 연속합 중 최댓값을 통해 dp테이블을 갱신하고,

해당 dp테이블에서의 최댓값이 구하고자하는 연속합이 된다. 

 

# 1912번: 연속합
n = int(input())
arr = list(map(int, input().split()))

dp = [-1001] * 100001

dp[1] = arr[0]
temp = dp[1]

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

print(temp)