**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`

.

**Solution:**

DP

public class Solution { int[] end; public int maxSubArray(int[] nums) { end = new int[nums.length]; if (nums.length < 2) return nums[0]; end[0] = nums[0]; for (int i = 1; i < nums.length; i++) { int connect = end[i-1] + nums[i]; int alone = nums[i]; end[i] = connect > alone ? connect : alone; } int max = end[0]; for (int i = 1; i < nums.length; i++) { if (end[i] > max) max = end[i]; } return max; } }