×

 0 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. asked 22 Mar '16, 00:54 81●11 accept rate: 22%

 0 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. answered 22 Mar '16, 03:51 3★akshayv3 157●8 accept rate: 4%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×2,214

question asked: 22 Mar '16, 00:54

question was seen: 1,758 times

last updated: 22 Mar '16, 03:51