[Kickstart][2019]2. Mural

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051060/0000000000058b89

---

부분합으로 풀었다.

벽은 가장자리부터 파괴되고 벽의 총 N개라고 했을 때 최대 (N+1)/2 개의 벽을 칠할 수 있다.

즉, 문제를 간단하게 보면 연속되는 (N+1)/2개의 벽을 선택할 때 구할 수 있는 최대 값을 구하는 문제이다.

부분합 배열을 sum, (N+1)/2를 cnt라고 했을 때, sum[i] - sum[i-cnt]가 (N+1)/2개의 벽을 선택했을 때의 가치이고. 

i 범위가 [cnt, N] 일 때 구한 가치 중 최대 값이 정답이 된다.

시간 복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/3e0a056c21886042e7ea2b1233ed9310