[알고리즘] LeetCode Maximum Subarray JS

개요

 연속 부분 배열 중 가장 큰 값을 리턴하는 문제이다.

[-2,1,-3,4,-1,2,1,-5,4] => [4,-1,2,1] => 6

Maximum Subarray - LeetCode

 

 

풀이

처음 투포인터가 떠올라 순차적으로 계속해서 접근해나갈때 왼쪽 포인터를 옮기는 조건을 도저히 찾을 수 없었다.

 

계속 고민하다가 못 풀어서 다른 사람의 풀이를 봤다. 잘 안풀렸던 부분이 값을 비교해나가며 교체하는 반복문 안 구조였다.

 

연속된 배열이기 때문에 이전 값을 계속해서 가져와 비교했어야했는데 잘 풀어낼 수 없었다.

연속된 값들을 계속 가져와 더한 값이 더 큰지 아니면 현재 들어오는 단일값이 더 큰지 비교해야한다는 것을 확인하면 쉽게 이해할 수 있었다

/**
 * @param {number[]} nums
 * @return {number}
 *
 * 배열 원소들 중 가장 큰 값을 가지는 연속 부분 배열을 리턴해라 X
 * 값을 리턴해라 최댓값
 */
var maxSubArray = function (nums) {
  let prev = 0;
  let answer = Number.MIN_SAFE_INTEGER;

  for (const num of nums) {
    // 이전값들에 대해서 정보를 저장하고 있어야한다 -> 전체 nums에서 연속된 배열이어야하기 때문이다.
    // 따라서 prev값이 현재 값을 포함한 연속된 배열이 더 큰지 아니면 단순히 현재 들어오는 값 하나가 더 큰지를 비교해서
    // 연속된 배열의 크기와 단순히 배열 원소 하나의 크기를 비교해서 최댓값을 찾는게 문제이다
    prev = Math.max(prev + num, num);
    answer = Math.max(answer, prev);
  }

  return answer;
};