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로 구현//분할 정복 코드 추가!

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;
	}
}