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.


  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];
                maxEndwith[i] = A[i];
            max = Math.max(max, maxEndwith[i]);
        return max;

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 )

Google+ photo

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


Connecting to %s