SubArray With sum zero.

Q: An array contain positive and negative elements, find maximum subarray whose sum is equal to zero.

Algorithm:

Lets take input array as a[]={-3,2,4,-6,-8,10,11}

Make an array b [] such that b[i]=b[i-1]+a[i]; means b[i] = sum(a[0],..., a[i]);

So b[]={-3,-1,3,-3,-11,-1,10}

Now all those pairs at indexes (i,j)in array b[] having equal numbers are the indexes of subarrays from (i+1,j) having sum as zero.

we have to find some (i, j) so: a[i] + a[i+1] + ... + a[j] = 0. But a[i] + a[i+1] + ... + a[j] = b[j] - b[i-1].
when creating the map using b values, the key in map is the value from b and the value in map is the index of from b. if a new key exists, this means we found a solution.

Finding all pairs in O(n) can be done by using map.

Working JAVA Code
---------------------------
import java.util.Comparator;
public class Index implements Comparable{
Integer start;
Integer end;
public Integer getStart() {
    return start;
}
public void setStart(Integer start) {
    this.start = start;
}
public Integer getEnd() {
    return end;
}
public void setEnd(Integer end) {
    this.end = end;
}
public int compareTo(Object index1) {
    index1 = (Index) index1;
    Index index2 = (Index) this;
    Integer  index1Distance = ((Index) index1).getEnd().intValue() -  ((Index) index1).getStart().intValue();
    Integer index2Distance = ((Index) index2).getEnd().intValue() -  ((Index) index2).getStart().intValue();
    if (index1Distance > index2Distance)
        return 1;
    else if (index1Distance == index2Distance)
        return 0;
    else
        return -1;
}
}

import java.util.HashMap;
import java.util.Map;
public class SubarraywithSumZero {
    public Index findLongestSubArraywithSumZero(long[] inputArray) {
        // 1. Generate a cummulative array
        for (int i=1; i < inputArray.length; i++) {
            inputArray[i] += inputArray[ (i-1)];
        }
        //2. Read the array, store it in map
        // For a subraary with 0 there should + and - numbers
        // we need to figure the longest distance indexes which have same numbers
        // since our array is cummulative postives and negatives which sum to 0 will bring the
        // intermittent array back to same number where it started
        // eg intermittent array = -6, -8, -10, -6, -4, 1, 2, 3, 4, 1
        // now from -6 we again reach -6
        // and later from 1 back to 1 which implies these two arrays are summing to 0
        // we just need the longest one
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        Index maxIndex = null;
        for (int i=0; i < inputArray.length; i++) {
            Integer index = new Integer(i);
            Integer val = new Integer((int) inputArray[i]);
            if (indexMap.get(val) == null) {
                indexMap.put(val, index);
            }
            else {
                if (maxIndex == null) {
                    maxIndex = new Index();
                    //collosion found the subarray
                    maxIndex.setStart(indexMap.get(val));
                    maxIndex.setEnd(new Integer(i));
                }
                else  {
                    Index index1 = new Index();
                    index1.setStart(indexMap.get(val));
                    index1.setEnd(new Integer(i));
                    if (maxIndex.compareTo(index1) <= 0) {
                        maxIndex = index1;
                    }
                }
            }
        }
            return maxIndex;       
    }
    public static void main(String[] args) {
        long inputArray[] = {3,2,4,-6,-8,10,11};
        SubarraywithSumZero subarraywithSumZero = new SubarraywithSumZero();
        Index maxIndex = subarraywithSumZero.findLongestSubArraywithSumZero(inputArray);
        System.out.println("Longgest Subarray with sum starts at [" + maxIndex.getStart() + " ] and ends at [" + maxIndex.getEnd() + "]");
    }
}