[LeetCode] [Easy] [JS] 53. Maximum Subarray

 

1. 문제

 

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 

 

 

2. 예시

 

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

 

 

 

3. 풀이

 

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

 

 

 

4. 결과

202 / 202 test cases passed.
Status: Accepted
Runtime: 52 ms
Memory Usage: 35.1 MB

 

 

 

5. 참고

 

Dynamic Programming, 카데인 알고리즘을 이용한다. 

자세한 내용은 이 글을 참고하세요.