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'..
2015. 3. 21.