30-Day LeetCoding Challenge - 3Day (Maximum Subarray )

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.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
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.

Solution

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
	int sum;
	for (int i = 0; i < nums.length; i++) {
		sum = nums[i];
		for (int j = i; j < nums.length; j++) {
			if (maxSum < sum) {
				maxSum = sum;
			}
			if (j < nums.length-1)
				sum += nums[j + 1];
		}
	}
	return maxSum;
   }
}

문제를 풀긴 풀었는데 이렇게 풀어버리면 O(n2)의 성능이 나온다.

문제에 보면 마지막 줄에 O(n)의 복잡도로도 해결할 수 있다고 나와있다.

도저히 내 머리로는 생각이 나지 않아서 구글링을 해 본 결과 카데인 알고리즘이라는게 나왔다.

이거 공부한 다음에 포스팅 해야겠다..

카데인 알고리즘 보러가기