Java O(n) way solution


#1
public class Solution {
    private int maxCount = 0;
	private int left = -1;
	private int right = -1;
	private boolean reset = true;

	public ArrayList<Integer> flip(String A) {
		int count = 0;
		int curLeft = 0;
		for(int i = 0; i < A.length(); i++) {
			if (A.charAt(i) == '0') {
				if (reset) {
					curLeft = i;
					reset = false;
				}
				count++;
			} else {
				if (count > maxCount) {
					maxCount = count;
					left = curLeft + 1;
					right = i;
				}
				if (count > 0) {
					count--;
				}
				else {
					count = 0;
					reset = true;
				}
			}
		}
		if (count > maxCount) {
			maxCount = count;
			left = curLeft + 1;
			right = A.length();
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (right > -1) {
			list.add(left);
			list.add(right);
		}
		
		return list;
    }
}