[2021/09/03][짤막한 이야기 - 최대구간합]

[2021/09/03][짤막한 이야기 - 최대구간합]
“최대 연속 부분합(Maximum Contiguous Subsequence Sum, MCSS)” 혹은 통칭 최대구간합은 자료구조 내의 구간합을 구하는 문제이다.
앞선 구간합(Prefix Sum)과는 조금 다르다.
최대구간합은 구간합처럼 “특정 범위의 합을 구하는 문제”가 아니라 “합이 최대가 되는 임의 범위의 합을 구하는 문제”라는 점이다.
따라서, 구간합과는 달리 최대구간합에서는 A배열 내 원소 변경이 없으며, 음수가 포함될 수 있다.
만약 양수만 포함된 배열이라면 전체 구간을 다 포함하는 것이 최대구간합이 될 것이다.
그림의 A배열에서는 A[2] ~ A[9]까지의 합이 14로 최대가 된다.
앞서 포스팅한 구간합 배열을 이용하여 최대구간합을 구할 수 있으며, 이 경우 시간 복잡도는 최대 O(N^2)이 된다.
모든 경우의 구간합을 서로 비교하여 최대값만 “Max”로 출력하는 방법이다.
배열 내 원소 변경이 없기 때문에 인덱스 트리를 사용하지 않아도 충분히 구현할 수 있다.
그런데 이것보다 더 빠른 최대구간합 확인 방법은 없을까?
[관련된 짤막한 이야기 - 구간합[2021/08/11]]
#이야기 #루니프 #알고리즘 #자료구조 #구간합 #최대구간합 #최대연속부분합 #MCSS

[2021/09/03][Short Story - Maximum Prefix Sum]
“Maximum Contiguous Subsequence Sum(MCSS)”, or so-called "Maximum Prefix Sum", is a problem of finding the prefix sum in a data structure.
It is slightly different from the prefix sum.
The point is that the maximum prefix sum is not a “problem of finding the sum of a specific range” like the prefix sum, but a “problem of finding the sum of an arbitrary range whose sum is the maximum”.
Therefore, unlike the prefix sum, in the maximum prefix sum, there is no element change in the A array, and negative numbers may be included.
If the array contains only positive numbers, the maximum prefix sum is to include the entire array.
In the A array in the figure, the sum of A[2] to A[9] is 14, which is the maximum.
The maximum prefix sum can be obtained using the previously posted prefix sum array, and in this case, the time complexity becomes maximum O(N^2).
This is a method in which only the maximum value is output as “Max” by comparing the prefix sum in all cases.
Since there is no change of elements in the array, it can be implemented without using an index tree.
But is there a faster way to check the maximum prefix sum than this?
[Related Short Story - Prefix Sum[2021/08/11]]
#Story #LootNiP #Algorithm #DataStructure #PrefixSum #MaximumPrefixSum #MaximumContiguousSubsequenceSum #MCSS