Keep it Real

https://app.codility.com/programmers/lessons/5-prefix_sums/ n 개의 숫자가 있고, m 개의 쿼리에 각 쿼리마다 a 인덱스부터 b 인덱스까지의 숫자의 합을 구하는 문제 숫자들의 합산을 저장하는 배열을 선언하고 n 개의 숫자 배열을 순회하며 합산을 저장한다. a 부터 b 까지의 숫자들의 합은 합산 배열의 b 인덱스 에서 a - 1 인덱스 값을 뺀 결과값이다. prefix sum 알고리즘을 이용하면 m * n 의 시간 복잡도를 m + n 으로 줄여준다.

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 posi..