Find the largest sum contiguous subarray.

Given an array of positive and negative integer s, find a contiguous subarray whose sum (sum of
elements) is maximized.

· Maximum subarray in an array is found in a single scan. We keep track of global maximum
sum so far and the maximum sum, which include the current element.
· When we find global maximum value so far is less than the maximum value containing
current value we update the global maximum value.
· Finally return the global maximum value.Concept of Stack
A stack is a memory in which values are stored and retrieved in “last in firs



import java.util.*;
class SumOfArray
{
public static void main(String[] args)
{
Scanner s=new Scanner(System.in);
System.out.println("enter size of Array");
int a=s.nextInt();
int[] arr=new int[a];
System.out.println("enter element of Array");
for(int i=0;i<a;i++)
{
                arr[i]=s.nextInt();
}
        System.out.println("Max sub Array sum:"+SumArray(arr,a));
}
public static int SumArray(int[] a,int size)
{
int maxsoFar=0,maxEnding=0;
for(int i=0;i<size;i++)
{
maxEnding=maxEnding+a[i];
if(maxEnding<0)
{
maxEnding=0;
}
if(maxsoFar<maxEnding)
{
maxsoFar=maxEnding;
}

}
return maxsoFar;
}

}