[2021/09/06][짤막한 이야기 - 최대구간합(개선)]

[2021/09/06][짤막한 이야기 - 최대구간합(개선)]
앞선 포스트에서 최대구간합에 대한 이야기를 하였다.
구간의 길이로 취할 수 있는 모든 경우에서 구간합 배열을 구하고, 그 중에서의 "Max"값을 출력하는 방식이였다.
구간합 배열을 모든 길이에 대하여 비교하기 때문에 O(N^2)의 시간 복잡도를 가졌다.
그러나 지금 제시하는 알고리즘은 동일한 결과를 출력하면서 시간 복잡도가 O(N)으로 개선된다.
이를 "카데인(Kadane)" 알고리즘이라고 한다.
비교 횟수를 효과적으로 줄일 수 있는 아이디어는 "각각의 최대구간합은 이전 최대구간합이 반영되어 있음"을 기반으로 한다.
즉 이전 최대구간합을 알 수 있다면 현재 인덱스에서의 최대구간합은 현재 인덱스의 값을 더함으로써 구할 수 있는 것이다.
정확한 원리를 이해하고 싶다면 예시 코드의 5번째 줄 아래에 "print(SubMax)"를 입력하여 중간 결과값을 검토하면 된다.
카데인 알고리즘은 이전 최대구간합으로 전체 최대구간합을 구하고, 최초 최대구간합을 0번째 배열값(Array[0])으로 설정한다.
즉, 이 알고리즘은 점화식으로 표현할 수 있는 동적계획법에 해당하는 기법이다.
[관련된 짤막한 이야기 - 최대구간합[2021/09/03]]
#이야기 #루니프 #알고리즘 #자료구조 #최대구간합 #카데인알고리즘

[2021/09/06][Short Story - Maximum Prefix Sum(Improvement)]
In the previous post, I talked about the maximum prefix sum.
In all cases that can be taken as the length of the subarray, it was a method of obtaining prefix sums and outputting the "Max" value among them.
It has a time complexity of O(N^2) because the sum array is compared for all lengths.
However, the present algorithm outputs the same result while improving the time complexity to O(N).
This is called the "Kadane" algorithm.
The idea of ​​effectively reducing the number of comparisons is based on the idea that "each maximum prefix sum reflects the previous maximum prefix sum".
That is, if the previous maximum prefix sum is known, the maximum interval sum in the current index can be obtained by adding the values ​​of the current index.
If you want to understand the exact principle, just type "print(SubMax)" below the 5th line of the example code to review the intermediate result.
The Kadane algorithm obtains the total maximum prefix sum from the previous maximum prefix sum and sets the first maximum prefix sum to the 0th array value (Array[0]).
That is, this algorithm is a technique corresponding to the dynamic programming method that can be expressed in the ignition equation.
[Related Short Story - Maximum Prefix Sum[2021/09/03]]
#Story #LootNiP #Algorithm #DataStructure #MaximumPrefixSum #KadaneAlgorithm