[leetcode]53. Maximum Subarray

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

연속된 부분 배열 중 합이 가장 큰 것을 찾는 문제.
매 순간 현재 위치까지의 최대 부분합을 유지하면서 전체 최대값을 업데이트 해 나가는 방식.
카데인 알고리즘 (Kadane's Algorithm)을 사용하면 가장 효율적으로 풀 수 있다.

순회를하며
currentSum = 아예 현재값부터 새로 시작하는게 나은지, 혹은 이전부분합에 현재값을 더하는게 나은지 비교한 값
maxSum = 현재까지의 maxSum과 currentSum 비교한 값

두 변수를 갱신하고,
순회 이후 maxSum을 리턴한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = nums[0];     // 전체 최대값
    let currentSum = nums[0]; // 현재까지의 부분합

    for (let i = 1; i < nums.length; i++) {
        // 이전 부분합에 현재값을 더하는게 나은지, 아니면 아예 현재값부터 새로 시작하는게 나은지 판단
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 전체 최대값 갱신
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
};

시간복잡도:O(n)

공간복잡도: O(1)