python 부분합, 연속 부분수열 최대합

python 부분합, 연속 부분수열 최대합

부분합

부분합은 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열(paritial_sum)입니다.

다음의 표를 보면 partial_sum을 미리 계산하면 특정 구간의 합을 O(1)에 구할 수 있습니다.

index	0	1	2	3	4	5
scores[]	100	95	80	100	70	65
partial_sum[]	100	195	275	375	445	510

예를 들어 3번째부터 5번째의 합을 구하고 싶다하면 partial_sum[5] - partial_sum[3-1] = 510-275 = 235를 구할 수 있습니다.

이 공식을 이용하면 구간합을 구할 수 있게 됩니다.

def partial_sum(arr, a, b):     arr = [0] + arr     partial_sum = [0] * len(arr)         for i in range(1, len(arr)):         partial_sum[i] = partial_sum[i-1] + arr[i]             partial_sum = partial_sum[1:]     print("partial_sum", partial_sum)         print("total sum", partial_sum[-1])         return partial_sum[b] - partial_sum[a-1]

위의 예제로 테스트 해보면 다음과 같습니다.

scores = [100, 95, 80, 100, 70, 65] partial_sum(scores, 3, 5) # 235 # partial_sum [100, 195, 275, 375, 445, 510] # total sum 510

연속 구간 부분수열 최대합

자 그러면 입력에 음수가 들어가는 경우에서 연속 구간 부분수열 최대합을 구해봅시다.

이때 최대를 구하려면 어떻게 해야할까요?

index	0	1	2	3	4	5	6
scores[]	-14	7	2	10	-4	9	-10
partial_sum[]	-14	-7	-5	5	1	10	0

인덱스 1~3까지의 부분합은 19, 1~5까지의 부분합은 24입니다. 여기서 연속 구간 부분수열 최대합은 24입니다.

부분합을 구하는 것은 비슷하고 max 최대치를 구간별로 탐색해야 합니다. 각 구간의 인덱스를 관리하기 위해서는 2중 for문을 써야하므로 O(N^2)가 되겠죠?

def partial_sum(arr):     arr = [0] + arr     partial_sum = [0] * len(arr)         for i in range(1, len(arr)):         partial_sum[i] = partial_sum[i-1] + arr[i]             partial_sum = partial_sum[1:]     print("partial_sum", partial_sum)         max_partial_sum = partial_sum[0]         for b in range(0, len(arr)-1):         for a in range(0, b):             print(a, b, partial_sum[b] - partial_sum[a-1])             max_partial_sum = max(max_partial_sum, partial_sum[b] - partial_sum[a-1])                 print("max partial sum", max_partial_sum)

위의 예제를 풀어보면

scores = [-14, 7, 2, 10, -4, 9, -10] print("list", scores) partial_sum(scores) # list [-14, 7, 2, 10, -4, 9, -10] partial_sum [-14, -7, -5, 5, 1, 10, 0] 0 1 -7 0 2 -5 1 2 9 0 3 5 1 3 19 2 3 12 0 4 1 1 4 15 2 4 8 3 4 6 0 5 10 1 5 24 2 5 17 3 5 15 4 5 5 0 6 0 1 6 14 2 6 7 3 6 5 4 6 -5 5 6 -1 max partial sum 24

동적 계획법

자 이제 동적 계획법을 적용해보죠

def dynamic_partial_sum(arr):     cache = [0] * len(arr)     cache[0] = arr[0]     for i in range(0, len(arr)):         cache[i] = max(0, cache[i-1]) + arr[i]         print(i, arr[i], cache)     print(cache)     return max(cache)

scores = [-14, 7, 2, 10, -4, 9, -10] print("list", scores) dynamic_partial_sum(scores) # list [-14, 7, 2, 10, -4, 9, -10] 0 -14 [-14, 0, 0, 0, 0, 0, 0] 1 7 [-14, 7, 0, 0, 0, 0, 0] 2 2 [-14, 7, 9, 0, 0, 0, 0] 3 10 [-14, 7, 9, 19, 0, 0, 0] 4 -4 [-14, 7, 9, 19, 15, 0, 0] 5 9 [-14, 7, 9, 19, 15, 24, 0] 6 -10 [-14, 7, 9, 19, 15, 24, 14] [-14, 7, 9, 19, 15, 24, 14]