53.Maximum Subarray

문제링크: https://leetcode.com/problems/maximum-subarray/

Subarray의 합이 가장 큰 결과를 반환하는 문제다.

Solution

Iteration O(n)

index a~b의 Subarray의 합은 b까지의 합 - a까지의 합이다. 따라서 b로 끝나는 array의 최대 subarray 합을 구하기 위해 b-1까지의 합 중 최소를 찾아내면 된다. 이 합은 단순하게 반복문과 비교를 통해 구할 수 있다.

Algorithm

• i번째 까지의 합을 담는 curSum, i - 1까지의 합 중 가장 작은 값을 minSum이라고 한다.
• 끝이 i번째로 끝나는 배열의 subarray합의 최대는 curSum - minSum이 된다.
• 반복을 통해 i - 1 까지의 curSum과 minSum을 비교해 더 작은 minSum을 구한다.
• curSum을 갱신하고 curSum - minSum을 저장해놓은 result와 비교해 더 큰 값을 result에 저장한다.

var maxSubArray = function(nums) {
    // i까지의 합 - i전 까지 합 중에 가장 작은 값
    let curSum = nums[0];
    let minSum = 0;
    let result = nums[0];
    for (let i = 1; i < nums.length; i++) {
        minSum = Math.min(minSum, curSum);
        curSum += nums[i];
        result = Math.max(result, curSum - minSum);
    }
    return result;
};