Iahub got bored, so he invented a game to be played on paper.
He writes n integers a1,?a2,?...,?an. 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 ak for which their positions are in range [i,?j] (that is i?≤?k?≤?j). Flip the value of xmeans 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.
The first line of the input contains an integer n (1?≤?n?≤?100). In the second line of the input there are n integers: a1,?a2,?...,?an. It is guaranteed that each of those n values is either 0 or 1.
Print an integer ― the maximal number of 1s that can be obtained after exactly one move.
In the first case, flip the segment from 2 to 5 (i?=?2,?j?=?5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].
In the second case, flipping only the second and the third element (i?=?2,?j?=?3) will turn all numbers into 1.
解題思路：題意是講有1個(gè)0,1序列，現(xiàn)允許你對(duì)任意1個(gè)子序列取反，問操作后得到的序列，最多能有多少個(gè)1。
數(shù)據(jù)不大，直接暴力。直接兩層循環(huán)枚舉取反序列的出發(fā)點(diǎn)和終點(diǎn)，統(tǒng)計(jì)每種情況下1的個(gè)數(shù)，保存1個(gè)最大值便可。
AC代碼：
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
