문제
풀이
문제를 풀기위해 모든 경우의 수를 비교하는 방법도 있지만, n <= 100,000 이라는 조건 때문에 불가능합니다. 모든 경우의 수를 따지지 않고 해결하기위해 다이나믹프로그래밍을 이용하여 빠르게 해결할 수 있습니다.
우리가 구하고자 하는 최대 연속합을 이루는 수열을 max_arr라 하고, 0 <= i <= n이라 할때
수열이 i-1번째 수까지 있는 경우와 i번째 까지 있는 경우를 비교해 봅시다.
두 경우에 max_arr가 같을까요? i번째 수가 추가되어 달라질까요?
사실 2가지 경우 모두 존재할 수 있습니다. 두 경우 모두 생각해봅시다.
case1: i번째 수가 추가되어도 max_arr이 유지되는 경우
case2: i번째 수가 추가되며 max_arr가 변경되는 경우
case1이라면 i번째 수는 max_arr에 여전히 포함되지 않아 i-1번째 수까지 있는 경우와 같고
case2라면 i번째 수가 새로운 max_arr에 포함되어 i-1번째 수까지 있던 경우의 max_arr보다 커진 경우입니다.
case1과 case2를 결정하기 위해서는 i번째 수를 포함하는 최대 연속합을 찾고 그 값이 새로운 max_arr이 되는지 이전의 max_arr과 비교해야 합니다.
i번째 수를 포함하는 최대연속합을 current_max[i]에 저장하고
i번째 수까지 있는 경우의 max_arr의 합을 저장하는 total_max[i]를 만들어 비교합니다.
- i-1번째 수까지 있는 경우의
max_arr:total_max[i-1] - i번째 수를 포함하는 최대연속합 :
current_max[i] - i번째 수까지 있는 경우의
max_arr=>total_max[i] = max(total_max[i-1], current_max[i])
그렇다면 current_max[i]는 어떻게 구해야 할까요?
입력으로 주어지는 수열에 음수도 포함되기 때문에 current_max는 단순히 누적합을 적을 수 없습니다.
current_max[i-1]이 음수인 경우 current_max[i]는 i번째 수 하나만 가지고 있는 것이 가장 큰 수일 것입니다.
이를 고려하여 current_max[i] = max(current_max[i-1] + arr[i], arr[i]) 로 정리할 수 있습니다. (arr[i]는 i번째 수)
정리하자면
current_max[i]: i번째 수를 포함하는 최대 연속합
total_max[i]: i번째 수를 추가했을 때의 전체 배열의 최대 연속합
코드
import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
total_max = {0:a[0]}
current_max = {0:a[0]}
for i in range(1,len(a)):
current_max[i] = max(current_max[i-1]+a[i], a[i])
total_max[i] = max(current_max[i], total_max[i-1])
print(total_max[n-1])참고
