LeetCode, Maximum Subarray (Java)

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

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.

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

완전탐색 분할정복등 다양한 방법으로 해결하 수 있지만
Kadane's Algorithm을 이용하면 동적계획법으로 O(n)으로 해결할 수 있다.

class Solution {
	public int maxSubArray(int[] nums) {
		int answer = nums[0];
		int currentSum = nums[0];

		for (int i = 1; i < nums.length; i++) {
			currentSum = Math.max(currentSum + nums[i], nums[i]);
			answer = Math.max(currentSum, answer);
		}

		return answer;
	}
}