/**
 * 
 * @author Mahsa Sadi
 * 
 * @since 2020 - 04 - 08
 * 
 * License: Creative Commons
 * 
 * Copyright by Mahsa Sadi
 *
 */
public class MaxSumSubArrayFinderV1 implements MaxSumSubArrayFinder {

	
	
	/**
	 * Problem : Maximum Sub-Array
	 * 
	 * 
	 * 
	 * 
	 * Description:
	 * Given an integer array nums, 
	 * find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
	 * 
	 * 
	 * Solution:
	 * 
	 * 1- Start from the beginning of the array. 
	 * 
	 * 2- Add the elements to the maximum sub-array one by one.
	 * 
	 * 3- Compare the sum of the elements with the maximum sum.
	 * 
	 * 4- Update the maximum sum if required.
	 * 
	 * 5- As soon as the sum of the elements gets negative,
	 *    reset sum to zero.
	 *    
	 * 6- Continue (Go to 2-).
	 * 
	 * 
	 */
	int maxSum, sum;
	boolean maxSumSet = false;
	
	
	@Override
	public int maxSubArray(int[] nums) {
		
		maxSum = sum = 0;
		
		for (int i = 0; i < nums.length; i++)
		{
			sum += nums [i];
			
			if (sum > maxSum || ! maxSumSet)
			     {
				    maxSum = sum;
			        maxSumSet = true;
			     }
			
			if (sum < 0)
			  sum = 0;
		}
	
		return maxSum;
	}

}