연속합
Prob
n개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합
Solv
- q에 p를 하나씩 추가하여 기존값 누적합 비교 후 큰 경우에만 누적
\(O(\frac{N^2}{2})\) 시간 초과 - 누적합 비교
\(O(N)\)Check
1.
| p | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
|---|---|---|---|---|---|---|---|---|---|---|
| q | 6 | -1 | 4 | 6 | 11 | -29 | -23 | 33 | 20 | |
| 9 | 0 | 9 | 12 | -24 | -17 | -2 | 32 | |||
| 10 | 5 | 15 | -23 | -12 | 4 | -3 |
2.
| p | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
|---|---|---|---|---|---|---|---|---|---|---|
| q | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| 10 | 6 | 9 | 10 | 15 | 21 | -14 | 35 | 34 |
