PROBLEM LINK:
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.