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

I am trying to solve this problem using kadane’s algorithm, but It is not passing pretest, whereas it is running fine on my system. Give it a try.

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

I am trying to solve this problem using kadane’s algorithm, but It is not passing pretest, whereas it is running fine on my system. Give it a try.

Step 1 : Count the no. of ones in the original array (let this be denoted by **o1**)

Step 2: Make another array which only contains 1 and -1 (insert 1 in new array wherever 0 is there in original array and insert -1 in new array wherever 1 is there in original array)

Step 3: Apply **Kadane’s Algorithm** in **new** array to find maximum sum subarray(let this maximum sum be **m1**)

Step 4:Calculate answer by adding **o1** to **m1**

Step 5:Submit and get accepted.

Step 6:**Enjoy**.

**Explanation** of **Step 2**: No matter which segment we select , after flipping that segment we are going to get certain no. of ones and certain no. of zeroes in that segment. Initially in any randomly selected segment ,let there be **a** one’s and **b** zeroe’s. After flipping that segment let the no.of ones be **a1** and no. of zeroes be **b1**. Let the no. of ones outside that segment be **a2** . Initially, the **total** no. of ones are **a(inside segment)+a2(outside segment)**.After applying flip the **total** no. of ones are [**a1(inside segment)+a2(outside segment)** = **o1(Step 1)+delta(+ve or -ve)**]. Till here we can conclude that after flipping any random segment the total no. of ones will be (**original no of ones + delta**).Here delta is (a1-a). Since the original no. of ones are constant,our ultimate goal now is to maximize *delta* i.e a1-a=b-a which can be done via step 2 and step 3.