53. Maximum Subarray

• Brute Force : O(n^2) 알고리즘
  : 그냥 구하는 방법 누적합을 이용하는 방법
  

• Divide & Conquer : O(nlogn) 알고리즘
  : Divide를 한 후 Conquer를 할 때 경계선 중심으로 확장하는 기법

• Scanning : O(n) 알고리즘
  : Kadane's Algorithm : 투 포인터 / 슬라이딩 윈도우 기법
  

Kadane's Algorithm

curSum = 0.

maxSum = arr[0] (첫번째 인덱스)

arr : [-2, 3, 2, -1]



curSum = curSum + arr[0]

curSum 비교 arr[0] : ( -2 = -2 )

curSum = -2

maxSum 비교 curSum : ( -2 = -2 )

maxSum = -2



curSum = curSum + arr[1]

curSum 비교 arr[1] : ( 1 < 3 )

curSum = arr[1] (3)

maxSum 비교 curSum : (3 > -2)

maxSum = 3

... 반복

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let curSum = 0;
  let maxSum = nums[0];

  for (let i = 0; i < nums.length; i++) {
    let tt = nums[i] + curSum;
    if (nums[i] >= tt) {
      curSum = nums[i];
    } else {
      curSum = tt;
    }

    if (maxSum <= curSum) {
      maxSum = curSum;
    }
  }

  return maxSum
};