Largest subarray with 0 sum O(n)

Largest subarray with 0 sum

time complexity O(n)

Basically we are adding the elements of the array and store tham in our map. 

The condition for adding the elements  in the map is

(i)if it is not present then add to the map with corresponding index ;

   

   4,  6,  3, -9, -5, 1, 3, 0, 2

   first insert 4 in map with index => 0 it will look like 4,0

   

   then add 6 to 4 and insert 10 with index =>1 it will look like 10,1

   then add 3 to 10 and insert 13 with index=>2 it will look like 13,2

   then add -9 to 13 and insert  4, but 4 is already present there it means the sum of all the                elements after first occurrence of 4 is 0 which are 6,3,-9 to get the length we subtract the              current index of element to previous occurrence element index  3-0=3 

   now we again sum the next element to getting the maximum length subarray 

   then add -5 to 4 and insert 1 with index=>4 it will look like -1,4

   then add 1 to -1 it results 0 it  means sum of all the element till this index is zero, so max-            length would be =index+1  5+1=6 because we are indexing from 0

   

   Similarly we calculate for the other elements ....

#include<stdio.h>

#include<map>

using namespace std;

int largest_subarray(int arr[],int len)

{

    int max_length=0;

    int sum=0,i;

    std::map<int, int> mymap;

    std::map<int,int>::iterator it;

    for(i=0;i<len;i++)

    {

        sum=sum+arr[i];

        if (arr[i]==0 && max_length==0)

            max_length = 1;

        if (sum == 0)

            max_length = i+1;

        if(mymap.find(sum)!=mymap.end())

        {

            max_length=max(max_length,i-mymap[sum]);

        }

        else

        {

            mymap[sum]=i;

        }

    }

    return max_length;

}

int main()

{

    int i,j,k;

    int arr[9]={4,  6,  3, -9, -5, 1, 3, 0, 2};

    int val=largest_subarray(arr,8);

    printf("%d",val);

    return 0;

}