LeetCode[JS] 53번 Maximum Subarray

💡문제링크

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

🔨풀이

처음에 dp로 풀어야 되나 하면서 접근했던거 같은데 한참을 뚫어져라 처다보니 규칙성을 찾을 수 있었다. nums 배열을 순회하면서 max값을 갱신하고 만약 다음 수를 더했을 때 0이하이면 여태 더한 sum값을 초기화하면 된다.  

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = nums[0]
    let sum = nums[0]
    let length = nums.length
    for(let i=1; i<length; ++i){
        if(sum<=0){
            sum=0
        }
        sum = sum + nums[i]
        max =Math.max(sum,max)
    }
    return max
};