이동식 저장소

Problem - 327A - Codeforces codeforces.com 0과 1로 이루어진 길이 $N$짜리 수열이 있다. 이 수열에서 연속된 구간 $[i,~j]$를 단 한 번만 골라 구간 안에 있는 모든 0을 1로, 1을 0으로 뒤집는다. 뒤집은 후에 1은 최대 몇 개 있을 수 있을까? 이 문제는 제한이 매우 작아서 $O(N^{3})$에도 풀 수 있지만, $N$이 커지더라도 풀 수 있는 방법을 생각해 보자. Maximum Subarray 먼저 Maximum subarray라는 개념을 알아야 한다. Maximum subaray는 배열의 끝 칸에서 끝나는 부분합 중 최댓값을 구하는 알고리즘이다. 식으로 쓰면 $ms[i]$는 $[1,~i]$ 구간에서 $i$를 포함하는 부분합 중 최댓값을 의미한다. 배열 ..