53. Maximum Subarray (javascript)

난이도 Easy 정답률 47%

간단히 설명해서 연속된 배열중에 가장큰 값을 반환하면 된다.

O(N)으로 풀이

다이나믹 프로그래밍에서 접근하기 쉬운 문제이다.

문제 접근을 Brute force로 하기 쉽다. 그렇게하면 2중포문을 돌려야 하기때문에 문제에서 O(N)을 만족하지 못 한다.

그렇다면 어떻게 접근 해야할까 카데인 알고리즘을 떠올려보자 잘 모른다면
https://www.youtube.com/watch?v=86CQq3pKSUw&t=404s&ab_channel=CSDojo
CSDojo 센세의 강의를 들어보자. (영어 모른다면 -> 자동자막 -> 설정 -> 자동번역 설정 -> 한국어)
Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1
Example 5:

Input: nums = [-100000]
Output: -100000

풀이코드:

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);
};