// 题目：给一个只有0，1的数组，求0，1相等的最长子串
// 解法：出现一个1就index减1，出现0就加1，构建index数组
//因为0，1数量相同的子串，index对应位置的值应该加减了相同数量的1和0，所以值相等
//问题变成了求index数组中相等值之间的最长距离问题
public class Main {
public static void main(String[] args) {
System.out.println(findMaxSeq(new int[] { 1,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1 }));
}
public static int findMaxSeq(int[] input) {
int temp = 0;
int[] index = new int[input.length];
int[] sum = new int[2*input.length+1]; //存储index值第一次出现的位置，因为index的范围是-N~N，所以sum的大小是2*input.length+1
for(int i = 0;i<sum.length;i++){
sum[i] = -1; //将sum中index第一次出现的位置都初始化为-1
}
int current = 0;
int result = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] == 1) {
temp--; //如果出现一个1就temp--
index[i] = temp;
if(sum[temp+input.length]!= -1){ //如果这个sum值之前出现过，就计算两次出现之间的距离，也就是这个子串的长度
current = i-sum[temp+input.length];
}else{ //如果这个index值之前没有出现过就是第一次出现，将值对应的下标写到sum数组中
sum[temp+input.length] = i;
}
} else {
temp++;
index[i] = temp;
if(sum[temp+input.length]!= -1){
current = i-sum[temp+input.length];
}else{
sum[temp+input.length] = i;
}
}
if(current>result){ //用当前子串长度与累计最长的子串长度比较，如果更长则更新当前的值
result = current;
}
}
return result;
}
}
