https://codility.com/media/train/7-MaxSlice.pdf
Prefix Sum 을 이용하는 방법은 O(n^2) 의 시간 복잡도가 걸린다.
O(n) 의 시간 복잡도가 걸리는 다른 방식이 있다.
9.3. Solution with O(n) time complexity This problem can be solved even faster. For each position, we compute the largest sum that ends in that position. If we assume that the maximum sum of a slice ending in position i equals max_ending, then the maximum slice ending in position i+1 equals max(0, max_ending+ ai+1). 9.4: Maximal slice — O(n). 1 def golden_max_slice(A): 2 max_ending = max_slice = 0 3 for a in A: 4 max_ending = max(0, max_ending + a) 5 max_slice = max(max_slice, max_ending) 6 return max_slice This time, the fastest algorithm is the one with the simplest implementation, however it is conceptually more difficult. We have used here a very popular and important technique. Based on the solution for shorter sequences we can find the solution for longer sequences.
'공부 > Algorithm' 카테고리의 다른 글
| Prefix Sum 알고리즘 (0) | 2023.05.06 |
|---|