最大连续区间和

1756: Vijos1083 小白逛公园 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss]

题目链接 题意：给出n个数,m个修改，每次修改后询问整个区间的最大连续子段。

http://codeforces.com/contest/327/problem/A 题意：给定一段序列，只由0,1组成。要求选一段非空区间，做翻转操作（0变1,1变0），问变完之后1最多能有多少。 思路：最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那么我们只要找到某一个区间内，0的个数-1的个数有最大值即可。如果a[i]==0的时候令b[i]=1，否则b[i]=0,那就是经典了最大连续区间和的问题了。dp的思想o(n)可以解决。