[자바스크립트/알고리즘] Leetcode - 부분 배열의 최대합

[문제] 53. Maximum Subarray

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

 

[예시]

Input	Output
[-2,1,-3,4,-1,2,1,-5,4]	6
[1]	1
[5,4,-1,7,8]	23

 

[풀이]

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

반복문을 돌면서 nums[i]의 값과 nums[i]+nums[i-1]을 비교한다. 그 둘 중 큰 값을 nums[i]에 넣는다.

이렇게하면 기존 값들과 다른 값들을 가진 nums (nums[0] 제외) 가 만들어진다.

이 배열 중에 가장 큰 값을 반환하면 된다.