public int maxSubArray(int[] nums) {

int n = nums.length;

if (n == 0) {

return 0;

}

int[] dp = new int[n];

dp[0] = nums[0];

for (int i = 1; i < n; i++) {

dp[i] = Math.max(nums[i], Math.max(dp[i-1] + nums[i], nums[i-1] + nums[i]));

}

int max = Integer.MIN_VALUE;

for(int i = 0; i < dp.length; i++) {

if(dp[i] > max) {

max = dp[i];

}

}

return max;

}

/**

public int maxSubArray2(int[] A) {

int max = Integer.MIN_VALUE, sum = 0;

for (int i = 0; i < A.length; i++) {

if (sum < 0)

sum = A[i];

else

sum += A[i];

if (sum > max)

max = sum;

}

return max;

}

// divide-and-conquer

public int maxSubArray3(int[] nums) {

if (nums == null || nums.length == 0) return 0;

return maxSubArray(nums, 0, nums.length-1);

}

private int maxSubArray(int[] nums, int left, int right) {

if (left > right) return Integer.MIN_VALUE;

if (left == right) return nums[left];

int mid = (left + right) / 2;

int L = maxSubArray(nums, left, mid-1);

int R = maxSubArray(nums, mid+1, right);

int leftSum = 0;

int tmp = 0;

for (int i=mid-1; i>=left; i--) {

tmp += nums[i];

if (tmp > leftSum) leftSum = tmp;

}

tmp = 0;

int rightSum = 0;

for (int i=mid+1; i<=right; i++) {

tmp += nums[i];

if (tmp > rightSum) rightSum = tmp;

}

return Math.max(Math.max(L, R), leftSum + rightSum + nums[mid]);

}

public static void main(String[] args) {

MaximumSubarray53 ms = new MaximumSubarray53();

System.out.println(ms.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));

System.out.println(ms.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 8}));

System.out.println(ms.maxSubArray(new int[]{-2, -1}));

System.out.println(ms.maxSubArray(new int[]{8, -19, 5, -4, 20}));

}