[LeetCode] 6. Maximum Subarray (brute force, kadane's algorithm)

Maximum Subarray

link :  leetcode.com/problems/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 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 = [-100000]
Output: -100000

문제설명

배열 값 조합 중 최댓값을 만들어내내는 연속적인 배열과 최댓값은 얼마인가

즉, 부분배열의 합 중 최댓값

Brute force

처음 생각해낸 것은 모든 부분 집합의 합을 구해서 비교해보는 것이었다.

가령 집합 [1,2,3]가 있을때

1

1+2

1+2+3

2

2+3

3

이렇게 모든 조합의 수를 계산하면서 max값을 갱신하는 방법이다.

이렇게 될경우 시간복잡도가 O(n^2)이 되어 매우 느린 알고리즘이 된다.

찾아보니 이 방법을 Brute Force알고리즘, 완전 탐색 알고리즘이라고 하더라

구현 방법은

class Solution {
    public int maxSubArray(int[] nums) {
        int max=Integer.MIN_VALUE; //-2147483648 정수로 나올수 있는 최소값
        int sum;
        int len=nums.length;
        if(len==1) //1인 경우 제외하기
        {
            return nums[0];
        }
        for(int i=0;i<len;i++)
        {
            sum=0;
            for(int j=i;j<len;j++)
            {              
                sum+=nums[j];
                max=Math.max(sum,max); //계속해서 더해가면서 max값 갱신
            }

        }
        return max;
    }
}

카데인 알고리즘

더 쉬운 방법이 없을까 찾아보다가 Kadane's Algorithm이란 것을 찾게 되었다.

카데인 알고리즘은 동적 알고리즘을 활용한 풀이법인데 한마디로 쉽게 표현하자면

A[k]로 끝나는 최대구간합은 A[k-1]로 끝나는 최대구간합에 A[k]값을 더한 값이므로 이 절차를 반복하면서 max를 구하는 과정인 것이다. (한마디가 좀 길다 미안하다.)

의사코드

A[K]로 끝나는 최대구간 합 = S
S[K] = A[K]로 끝나는 최대 구간합
S[K] = MAX(S[K-1] + A[K], A[K]) // A[K]가 더 클수도 있음
S[0] = A[0]로 끝나는 최대구간합이므로 S[0]값은 A[0]값이다.

구현

class Solution {
    public int maxSubArray(int[] nums) {
        int tempMax = 0;
        int max = Integer.MIN_VALUE;

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

            if(tempMax + nums[i] < nums[i]){
                tempMax = 0; 
            } //i번째까지 더한 값이 i번째 값보다 작다면 i가 제일 큰 값이다.
            tempMax += nums[i]; //tempMax는 i-1번째까지 더한값의 최대값이 될것이다.

            if(tempMax > max){
                max = tempMax;
            }
        }

        return max;
    }
}

느낌적인 느낌은 알겠는데 이걸 혼자 다시 구현해보라고 하면 못할것 같은 느낌이다;;

카데인 알고리즘으로 계산하게 되면 시간복잡도는 O(n)이 된다.