[JS] LeetCode - 53. Maximum Subarray / 카데인 알고리즘(Kadane's Algorithm)

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.

A subarray is a contiguous part of an array.

Input, Output 예시

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

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23

 

풀이

처음에 그냥 Brute-Force로 생각을 했는데 그렇게 하면 O(n)의 시간복잡도를 만족하지 못할 것 같아서 고민했다. 

 

먼저 브루트 포스 방법으로는 아래와 같이 풀어보았다. 이렇게 하면 시간복잡도는 O(n^2)이다.

var maxSubArray = function(nums) {
    let answer=nums[0];
    for(let i=0;i<nums.length;i++){
        let sum=nums[i];
        for(let j=i+1;j<nums.length;j++){
            sum+=nums[j];
            answer = Math.max(sum, answer);
        }
    }
    return answer;
};

 

찾아보다가 이 문제는 동적 프로그래밍, 카데인 알고리즘을 쓰면 되는 문제라는 것을 알았다.

카데인 알고리즘(Kadane's Algorithm)은 다이나믹 프로그래밍을 적용한 방식이다.

 

여기서 다이나믹 프로그래밍(Dynamic Programming)이란 주어진 문제를 풀기 위해 문제를 여러 개의 하위 문제(subproblem)로 나눠서 푼 다음, 그것을 결합해 최종 목적에 도달하는 것이다.

다이나믹 프로그래밍의 핵심은 큰 문제를 작은 문제로 쪼개어 해결하고, 한번 풀었던 문제는 어딘가에 저장해두었다가 반복해서 풀지 않는 것이다.

https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29

 

유튜브에 CS Dojo님이 설명해주신 영상. 영어 자막을 켜놓고 보니 편하게 볼 수 있었다. 워낙 잘 설명해줘서 이것만 보면 될 것 같다!

https://youtu.be/86CQq3pKSUw

Kadane's Algorithm to Maximum Sum Subarray Problem

카데인 알고리즘을 이용한 코드

var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    };
    return Math.max(...nums);
};