MAXZEROS - editorial

PROBLEM LINK:

Practice
Contest

Author: Mahmoud Badawy

Tester: Mohammed Ehab

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP, Two pointers, Back Tracking

PROBLEM:

Given a binary string find a substring that have the maximum (number of zeros-numer of ones)

QUICK EXPLANATION:

using DP find this value then using BackTracking find the interval

EXPLANATION:

You can use the following DP to find the maximum value

DP[i][0]=maximum value you can get if you skipped the first i elements

DP[i][1]=maximum value if you have used some of the first i elements

then DP[i][0]=max(DP[i+1][0],DP[i+1][1]+arr[i])

and DP[i][1]=max(DP[i+1][1]+arr[i],0)

and you should handle the special case when the string is only ones
Complexity: O(n)

ALTERNATIVE SOLUTION:

You can use two pointers method to find the best answer
Complexity: O(n)

SOLUTIONS:

DP solution can be found here.

Two Pointers solution by Elbatanony can be found here.