# Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution using the **divide and conquer** approach, which is more subtle.

> **Example 1:**\
> **Input :** nums = \[-2,1,-3,4,-1,2,1,-5,4]\
> **Output : 6**\
> **Explanation :** \[4,-1,2,1] has the largest sum = 6.

> Example 2:\
> Input : nums = \[1]\
> Output : 1

> Example 3:\
> Input : nums = \[0]\
> Output : 0
>
> Example 4:\
> Input : nums = \[-1]\
> Output : -1
>
> Example 5:\
> Input : nums = \[-2147483647]\
> Output : -2147483647

**자료구조**\
정수 타입 변수 2개\
**알고리즘**\
Math.max(a,b)를 이용하여 더 큰 값을 채택한다. new를 포함할지 말지, new부터 다시 시작할지 말지를 선택한다.

**알고리즘을 Java로 구현//분할 정복 코드 추가!**

```java
package java_basic;

public class MaxSubArray {

	public static void main(String[] args) {
		int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		System.out.println(maxSubArray(nums));
	}

	public static int maxSubArray(int[] nums) {
		int newSum = nums[0];
		int max = nums[0];

		for (int i = 1; i < nums.length; i++) {

			newSum = Math.max(newSum + nums[i], nums[i]);
			max = Math.max(max, newSum);
		}
		return max;
	}

	public static int maxSubArray_dp(int[] A) {
		int n = A.length;
		int[] dp = new int[n];// dp[i] means the maximum subarray ending with A[i];
		dp[0] = A[0];
		int max = dp[0];

		for (int i = 1; i < n; i++) {
			dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
			max = Math.max(max, dp[i]);
		}

		return max;
	}
}

```