# Share my DP&Map solution, one pass

• ``````public int findMaxLength(int[] nums) {
int n = nums.length, res = 0;
Map<Integer, Integer> map = new HashMap<>();
int[][] dp = new int[n+1][2];
for (int i = 1; i < dp.length; i++) {
if (nums[i-1] == 0) {
dp[i][0] = dp[i-1][0]+1;
dp[i][1] = dp[i-1][1];
}else {
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1]+1;
}
if (dp[i][0] == dp[i][1]) res = Math.max(res, dp[i][0]*2);
else {
int dif = dp[i][1]-dp[i][0];
if (map.containsKey(dif)) res = Math.max(res, 2*(dp[i][0]-dp[map.get(dif)][0]));
else map.put(dif, i);
}
}
return res;
}
``````

• @shawloatrchen Can you explain your logic? Thanks!

• If you want to do it in one pass, it can be done in a much simpler way:

``````    public int findMaxLength(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>() {{put(0,0);}};
int maxLength = 0, runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
Integer prev = map.get(2*runningSum-i-1);
if (prev != null) maxLength = Math.max(maxLength, i+1-prev);
else map.put(2*runningSum-i-1, i+1);
}
return maxLength;
}

``````

• @jamescsi
Use dp[][] to store the zeros and ones from start to current position
and use map to store the difference of ones and zeros with index;
if current position ones-zeros = 2, we check map if there is other position ones-zeros=2
if we find, the 2*(current index - that index) is candidate
the max candidate is the answer

• @shawloatrchen thanks a lot

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.