Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Solution

We need to find the maximum sum contiguous subarray here. Let’s start from the example above. Let’s keep track of sum and maxSum which is a very small number N. And start summing from the beginning –

• for -2, sum is -2, maxSum will still become -2.
• sum of -2 and 1 will be -1, A thing to note here is our new sum -1 is less than the current value 1. So our sum should become 1 and max between -2 and 1 is 1. Therefore our maxSum is also 1.
• sum of 1 and -3 is -2. maxSum between -2, 1 is 1.
• sum of -2 and 4 is 2, which is less than 4. so sum becomes 4. and maxSum becomes 4.
• And we keep doing this until we reach end.

Our basic algorithm will be

• Take two variables sum and maxSum to keep track of sum and maxSum till a given position in array.
• Loop through the array
  • sum is addition of sum and current value in the array. If sum < current value in the array, sum becomes current value in the array.
  • maxSum is maximum of maxSum and sum.
  • Repeat above steps until we reach the end of the loop.
• return the maxSum

/**
 * MaxSubArray.java
 * Purpose: Find maximum sum contiguous subarray 
 *
 * @author Megha Rastogi
 * @version 1.0 06/06/2020
 */
class MaxSubArray {
    
    /**
     * Find maximum sum contiguous subarray 
     *
     * @param Array, nums
     * @return integer, maxSum
     */
    public int maxSubArray(int[] nums) {
        
        // Initalize maxSum and sum
        int maxSum = Integer.MIN_VALUE, sum = 0;
        
        // Loop through the array
        for(int i = 0; i < nums.length; i++){
            
            // add current value to sum
            sum+=nums[i];
            
            // update sum if it becomes less than current value
            if(sum < nums[i])
                sum = nums[i];
            
            // update the max sum
            maxSum = Math.max(maxSum, sum);
        }
        
        //return the max sum
        return maxSum;
    }
}

Code – MaxSubArray.java

Source – Leetcode