### 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.