Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [โˆ’2,1,โˆ’3,4,โˆ’1,2,1,โˆ’5,4],
the contiguous subarray [4,โˆ’1,2,1] has the largest sum = 6.

public class Solution {
    public int maxSubArray(int[] nums) {
        //Kaden's algorithm 
        //The max sum in the first I elements is either:
        //(1) The first (i-1) elements + nums[i]
        //(2) nums[i]
        int maxSoFar = nums[0], maxEndHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndHere = Math.max(maxEndHere + nums[i], nums[i]);
            //maxSoFar keeps track of the sum of array which 
            //doesn't end at i.
            maxSoFar = Math.max(maxSoFar, maxEndHere);
        }
        return maxSoFar;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s