Блог пользователя shyam81295

Автор shyam81295, история, 9 лет назад, По-английски

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.

Теги #dp
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится