53. Maximum Subarray

var maxSubArray = function(nums) {
    let max = -100000000;
    let current = 0
    for(let i = 0; i < nums.length; i++) {
        current = Math.max(current + nums[i], nums[i])
        max = Math.max(max, current)
    }
    return max
    // 이전 누적값과 현재값 더한거랑 현재값이랑 비교해서 max에다가 비교한다
};

배열내에서 부분집합 배열들중에서 요소들의 총합이 가장 큰값을 구하는 문제이다.

처음에는 이중 for문으로 모든 배열들의 요소들의 합을 비교하는 로직으로 했지만 O(n^2) 시간 복잡도로 인해서 시간초과됐다..

저 로직으로는 한번의 for문으로 시간 복잡도가 O(n)으로 빠르게 구할 수 있다.

변수 current는 누적값과 현재 배열인덱스요소값과 비교해서 둘 중 큰값을 반환한다.

그리고 current값과 이전 max중 비교해서 큰값을 다시 max에다가 할당해주는 로직이다.