[Leetcode 12/100] Maximum Subarray - Easy

문제 풀이 방식

kadane's algorithm을 활용한 풀이

구간의 최대 합을 구하기 위해 사용할 수 있는 알고리즘으로 주요 수식은 아래와 같다.

S[i] = Math.max(arr[i], arr[i] + S[i-1])

S 배열은 이 구간까지의 최대 합으로 만약 최대 합보다 현재 인덱스 배열의 값이 크다면 초기화를 시켜주는 방식이다.

주의할 점

브루트 포스 방식으로 모든 배열을 탐색하게 될 경우 O(n^2)의 시간복잡도를 가진다.

그러나 시간을 그만큼 주지 않는 경우가 대부분이므로 O(n)으로 풀어야 success를 받을 수 있다.

소스코드

class Solution {
    public int maxSubArray(int[] nums) {
        
        if(nums.length == 0) return 0;
        
        int sum = nums[0];
        int res = nums[0];
        for(int i=1; i<nums.length; i++){
            sum = Math.max(nums[i] , sum + nums[i]);
            res = Math.max(res, sum);
        }
        return res;
    }
}