shyam81295's blog

By shyam81295, history, 6 years ago, In English

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
  • Vote: I like it
  • -6
  • Vote: I do not like it