top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

If an array contains positive and negative integers then how can we find largest subarray with sum as zero?

+5 votes
673 views
If an array contains positive and negative integers then how can we find largest subarray with sum as zero?
posted Nov 29, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
It's a standard bruteforce or backtrack problem other way is to use dynamic programming.

1 Answer

+1 vote

Try this method to get your result:

   public static Boolean printZeroSumSubarray(int arr[]) // return true when sub array sum is zero
    {
        // Creates an empty hashMap hM
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

        // Initialize sum of elements
        int sum = 0;        

        // Traverse through the given array
        for (int i = 0; i < arr.length; i++)
        {   
            // Add current element to sum
            sum += arr[i];

            // Return true in following cases
            // a) Current element is 0
            // b) sum of elements from 0 to i is 0
            // c) sum is already present in hash map
            if (arr[i] == 0 || sum == 0 || hM.get(sum) != null)                            
               return true;

            // Add sum to hash map
            hM.put(sum, i);
        }    

        // We reach here only when there is no subarray with 0 sum
        return false;
    }  

from this method you will get the different subarray and get thier length then print the subarray of maximum length.

answer Mar 22, 2016 by Shivam Kumar Pandey
Similar Questions
+6 votes

What is the simples way to check if the sum of two unsigned integers has resulted in an overflow.

+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

...