You are not logged in. Please login at www.codechef.com to post your questions!

×

Kadane's Algorithm Codeforces

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

abhiroj786's gravatar image

2★abhiroj786
8111
accept rate: 22%

edited 22 Mar '16, 00:55


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.

link

answered 22 Mar '16, 03:51

akshayv3's gravatar image

3★akshayv3
1578
accept rate: 4%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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