Kadane's Algorithm Codeforces

dynamic-programming
easy

#1

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.


#2

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.