aakarshmadhavan's blog

Simple DP problem involving maximization
By aakarshmadhavan, history, 6 years ago, In English 
Given an array arr[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1.You have to do atmost one “Flip” operation on a subarray. Then finally display maximum number of 1 you can have in the array.

I did not know this was a DP problem before I checked the tag. I am kind of confused how to proceed with the problem right now. Any ideas/hints are massively appreciated. So far I thought of some things which arent quite correct such as

  • DP[i] = Max # of 1's in subarray [0,...,i]
  • DP[i] = Max # of 1's in subarray [0,...,i] if you flip at index i

I am thinking second one might be an idea, but I can't find a optimal structure for "recursion."

Thanks

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Suppose you change the array: 0 is 1, and 1 is -1.

The array -1 1 1 1 -1 1 1 -1 is the same as the input array 1 0 0 0 1 0 0 1.

If some subarray has sum equals to X, it means that if you flip this subarray, you get X 1's more than your initial answer. So, with this information, the answer is related with the maximum subarray sum you can get.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi there,

    "If some subarray has sum equals to X, it means that if you flip this subarray, you get X 1's more than your initial answer. So, with this information, the answer is related with the maximum subarray sum you can get."

    Can you please explain why this is the case? Thank you very much

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      See the sum of some arrays and note that if the sum is positive, there are more 0's than 1's:

      1 -1 = 0. (Original array = 0 1)

      1 1 = 2. (Original array = 0 0)

      1 1 1 -1 1 1 = 4. (Original array = 0 0 0 1 0 0)

      Note that the 1's here are 0 on original array, and -1's are 1. If the array has sum X and X > 0, it means that there are more 0's than 1's.

      See what happens when you flip the whole array:

      On the first array, the sum is 0: after the flip, you get 0 more ones.

      On the second array: after the flip you get 2 more ones.

      On the third array: after the flip you get 4 more ones (you flip 5 0's to 1 and 1 1's to 0).

      Conclusion: if some subarray has sum X, it means that this subarray has X more 0's than 1's, and after the flip will have X more 1's than 0's. That's why you should flip the subarray with maximum sum. Note that it is not good flip an subarray with negative sum, because it has more 1's than 0's and after the flip it will decrease the answer.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Note that flipping a sub-array [l, r], where 1 ≤ l ≤ r ≤ n, should add S(l, r) to the total sum of the array T(n), where

The proof is simple:

→ Reply