Leetcode–Maximum Subarray

The Problem:

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.

Notes:

  1. A basic DP problem

Java Solution

public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length==0)return 0;
        int[] maxEndwith = new int[A.length];
        maxEndwith[0] = A[0];
        int max = maxEndwith[0];
        for(int i = 1; i < A.length; i++){
            if(maxEndwith[i-1] >0){
                maxEndwith[i] = maxEndwith[i-1] + A[i];
            }
            else{
                maxEndwith[i] = A[i];
            }
            max = Math.max(max, maxEndwith[i]);
        }
        return max;
    }
}
      
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