[LeetCode easy] Maximun Subarray JavaScript

https://leetcode.com/problems/maximum-subarray/

문제 설명

배열의 원소를 연속적으로 더했을 때 가장 큰 합이 되는 것의 합을 출력하면 된다.
예를 들어 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 일 때
4 -1 2 1 의 합인 6이 가장 크다.

문제 풀이

dp로 풀 수 있다. 현재의 최대값을 이전 값과 더 했을 때가 큰지 아니면 지금만 봤을 때 큰지를 확인해보면 된다.
예를 들어 저 위의 문제를 보면
처음은 -2이고 두 번째는 -2와 1을 더한 -1과 1 중에 어느게 더큰지 보면 된다. 1이 더 크니 그냥 1로 둔다. 다음은 1 - 3 vs -3 -2 가 더 크므로 -2. -2 + 4 vs 4 4가 더크므로 4. 이렇게 계속 하다보면 답을 구할 수 있다.

전꺼랑 지금꺼랑 더 했는데 더 작아질 경우에는 굳이 더할 필요 없이 자기꺼만 가지고 그다음으로 진행하면 되기 때문이다..

코드

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