FindMaxContinuousSubsequenceSumInArray

**********************************Using DP ***************************************************
/*
 * Question : Find the maximum continuous subsequence sum in an array
 * Source: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
 * 		   https://www.youtube.com/watch?v=hXlv88ddcgw&list=PL962BEE1A26238CA3
 */

package FindMaxContinuousSumInArray;

import java.util.Scanner;

public class UsingDynamicProgramming {
	
	    public static void main(String[] args){
	        Scanner in = new Scanner(System.in);
	        try{
	            System.out.println("Enter the number of array elements");
	            int n = in.nextInt();
	            int[] a = new int[n];
	            System.out.println("Enter the array elements");
	            for(int i=0;i<n;i++)
	                a[i]=in.nextInt();
	            System.out.println("The max sym in the array is: "+maxSum(a));
	        }
	        finally{
	        in.close();
	        }
	    }
	    public static int maxSum(int[] a){
	    
	    // We will solve this problem using Dynamic Programming
	    
	    if(a.length==0 || a==null)
	        return -1;
	    
	    int[] dp = new int[a.length];
	    dp[0] = a[0];
	    
	    for(int i=1;i<a.length;i++)
	        dp[i] = Math.max(dp[i-1]+a[i],a[i]);
	    
	    
	    // iterate over all the values of dp to find the max
	    int max = 0;
	    for(int element: dp)
	         max = Math.max(max,element);
	         
	     return max;       
	    }
	    /*
	    Analysis:
	    Time Complexity = O(n)
	    Space Complexity = O(n) which is used to store the dp array
	    */
	}
******************************* Using Kadane's Algorithm ******************************
/*
 * Question : Find the maximum continuous subsequence sum in an array
 * Source: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
 * 		   https://www.youtube.com/watch?v=hXlv88ddcgw&list=PL962BEE1A26238CA3
 * 
 * Algorithm:
 * Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far
 */

package FindMaxContinuousSumInArray;

import java.util.Scanner;

public class UsingKadanesAlgorithm {
	  public static void main(String[] args){
	        Scanner in = new Scanner(System.in);
	        try{
	            System.out.println("Enter the number of array elements");
	            int n = in.nextInt();
	            int[] a = new int[n];
	            System.out.println("Enter the array elements");
	            for(int i=0;i<n;i++)
	                a[i]=in.nextInt();
	            System.out.println("The max sum in the array is: "+usingKadanesAlgorithm(a));
	        }
	        finally{
	        in.close();
	        }
	    }

	private static int usingKadanesAlgorithm(int[] a) {
		if(a==null||a.length==0)
			return -1;
		
		int maxTillHere=0;
		int overallMax=0;
		
		for(int i=0;i<a.length;i++){
			maxTillHere = maxTillHere + a[i];
			if(maxTillHere<0)
				maxTillHere=0;
			overallMax = Math.max(maxTillHere, overallMax);
		}
		return overallMax;
		
	}
	/*
	 * Analysis:
	 * Time Complexity = O(n)
	 * Space Complexity = O(1)
	 */
}