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;

Leave a Reply

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

You are commenting using your 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