[C/C++] Codeforce 327A - Flipping Game

A. Flipping Game

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Iahub got bored, so he invented a game to be played on paper.

He writes n integers a 1, a 2, ..., a n. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values a k for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.

The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a 1, a 2, ..., a n. It is guaranteed that each of those n values is either 0 or 1.

Output

Print an integer — the maximal number of 1s that can be obtained after exactly one move.

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
int n, a;

	int cnt = 0, temp = 0, temp_max = -1; 
	// temp_max = -1인 이유는 만약 입력의 값이 모두 1일때(1 1 1 1....) 적어도 1번은 뒤집어야 하므로.
		
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		if (a == 1)
		{
			cnt++;
			if (temp > 0) temp -= 1;
		}
		else
		{
			temp++;
			if (temp > temp_max) temp_max = temp;
		}		
	}
	printf("%d\n", cnt + temp_max);
	

	return 0;
}

 

만약 입력값이

8

1 0 0 1 0 0 0 1 

이라고 예시를 든다면

Input	cnt	temp	temp_max
1	1	0	0
0	1	1	1
0	1	2	2
1	2	1	2
0	2	2	2
0	2	3	3
0	2	4	4
1	3	3	4

 

따라서 최댓값은 cnt+temp_max = 3+4 = 7이 된다.

temp은 항상 0 이상의 값을 유지하고 0이 나올 시 +1

1이 나올 시 -1을 해주어 0이 연속되면 연속될 수록 max 값이 높아지게 된다.

 

https://codeforces.com/problemset/problem/327/A

Problem - 327A - Codeforces