Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

327 a — Flipping game

Revision en1, by shyam81295, 2015-07-04 14:27:56

My first problem of Dynamic Programming

Logic: max (total_1s + max (number_of_0s_in_subarray))

The key to solve this problem is to make use of Kadane's Algorithm. Kadance's Algorithm basically is used to find the maximum sum in a contiguous subarray of an array.

Click here for link for Kadane's Algorithm Explanation

Also, important point to note is that : In input, atleast one number 0 is required for flipping purposes, but if all are 1s in input, then answer will be (total_1s — 1) because atleast one number should be flipped.

Tags #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shyam81295 2015-07-04 14:27:56 623 Initial revision (published)