kadane's algorithm(maximum contiguous subarray)

분명히 어디선가 봤던 문제였는데...

이렇게 볼때마다 새로운지...

내 기억력이 이렇게 짧다는 것을 다시 한번 확인했다.

내 기억력을 확인해 준 문제는...

maximum contiguous subarray problem

어떤 배열이 주어졌을 때, 배열에서 연속된 부분배열 중 가장 큰 합을 찾는 문제이다.

예를 들면,

array = [2, -1, 2, 3, 4, -5]

에서 maximum contiguous subarray는 [2, -1, 2, 3, 4] 가 되어 maximum은 10 이 된다.

어찌보면, 간단해 보이지만...

각 배열의 index에서 가능한 모든 sum을 구해야 한다고 생각하면 그리 쉽지 않다.

하지만, 이 문제의 해법과 관련된 유명한 알고리즘이 있는데...

그 알고리즘이 kadane's algorithm이다.

http://en.wikipedia.org/wiki/Maximum_subarray_problem

알고리즘을 간단히 설명하면, 1차원으로 이뤄진 배열에서 

배열을 한번 스캔하면서, 각 포지션에서 가지는 최대값을 구하는 그런 알고리즘이다.

(글로 적다보니... 내가 제대로 이해한 것인가에 대한 의문이 든다.)

좀 더 명확한 설명은 위에 있는 위키 링크를 보시길...

내가 풀었던 방법은 index가 필요한 계산은 아니였기에...

maximum sum만 확인하면서 문제를 해결한다.(find_contiguous_subarray() 참고)

아래에 있는 코드를 보며... 다음에는 이 문제를 보고 당황하지 않기를 바라며...

이 포스팅을 마무리한다.

#!/bin/python def find_contiguous_subarray(ary): max_sum, cur_sum = ary[0], ary[0] for i in xrange(1, len(ary)): if cur_sum < 0: cur_sum = ary[i] else: cur_sum = cur_sum + ary[i] if cur_sum > max_sum: max_sum = cur_sum return max_sum def find_non_contiguous_subarray(ary): ary = sorted(ary, reverse=True) max_sum = ary[0] for i, val in enumerate(ary): if i == 0: continue if max_sum + val > max_sum: max_sum += val else: break return max_sum def print_maximum_subarray(ary): contiguous_max_sum = find_contiguous_subarray(ary) non_contiguous_max_sum = find_non_contiguous_subarray(ary) print contiguous_max_sum, non_contiguous_max_sum T = input() while T > 0: N = input() ary = map(int, raw_input().split()) T -= 1 print_maximum_subarray(ary)