[LeetCode] 53. Maximum Subarray

최대 값인 Subarray의 합을 찾아내는 문제이다.

구현은 매우 간단하게 가능한데, O(n)의 시간복잡도 내에서 전체 배열을 순회하며

어느 타이밍에서 최대 합이 나오는지 매 요소마다 판별하면 됨

😎풀이

function maxSubArray(nums: number[]): number {
    // 현재까지의 최대 합
    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;
}