Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

JavaScript로 최대 곱을 갖는 연속 부분 배열 찾기

문제 소개

이번 글에서는 정수 배열(양수와 음수 모두 포함)을 인자로 받아, 그중 곱이 최대가 되는 연속 부분 배열(subarray)의 곱을 계산하여 반환하는 JavaScript 함수를 작성해 보겠습니다.

예를 들어 입력 배열이 다음과 같다고 가정해 봅시다.

const arr = [4, -5, 2, -3, 1, -4, 0, -3];

이 경우 기대되는 출력값은 다음과 같습니다.

const output = 120

그 이유는 곱이 가장 커지는 부분 배열이 바로 [4, -5, 2, -3]이고, 실제 곱을 계산하면 4 × (-5) × 2 × (-3) = 120이 되기 때문입니다. 음수 두 개가 곱해져 양수가 되면서 전체 곱이 커지는 전형적인 경우입니다.

핵심 아이디어: 동시에 최솟값도 추적하기

이 문제를 단순하게 접근하면 놓치게 되는 지점이 있습니다. 바로 음수의 존재입니다. 어떤 시점의 최댓값도, 다음 원소가 음수와 만나면 오히려 최솟값으로 뒤집힐 수 있습니다. 따라서 반복문을 진행하면서 다음 세 가지 값을 함께 관리해야 합니다.

  • max: 현재 위치에서 끝나는 부분 배열의 최대 곱
  • min: 현재 위치에서 끝나는 부분 배열의 최소 곱 (음수일 가능성 대비)
  • greatest: 지금까지 등장한 값 중 전역 최대 곱

각 단계에서는 '현재 원소 자체', '이전 최댓값 × 현재 원소', '이전 최솟값 × 현재 원소' 세 후보 중 가장 큰 것을 새로운 최댓값으로, 가장 작은 것을 새로운 최솟값으로 갱신합니다. 이때 max가 덮어씌워지기 전에 임시 변수 tempMax에 저장해 두는 것이 중요합니다.

구현 예제 코드

const arr = [4, -5, 2, -3, 1, -4, 0, -3];

const maxProduct = (arr = []) => {
   if (arr.length === 0){
      return 0;
   };
   let max = arr[0],
   min = arr[0],
   greatest = arr[0];
   for (let i = 1; i <= arr.length - 1; i++) {
      let tempMax = max * arr[i];
      max = Math.max(
         arr[i],
         Math.max(min * arr[i], max * arr[i])
      );
      min = Math.min(arr[i], Math.min(min * arr[i], tempMax));
      greatest = Math.max(greatest, max);
   }
   return greatest;
};

console.log(maxProduct(arr));

코드 동작 살펴보기

  1. 배열이 비어 있으면 곱을 정의할 수 없으므로 0을 즉시 반환합니다.
  2. 첫 번째 원소로 max, min, greatest를 초기화합니다.
  3. 두 번째 원소부터 순회하며 매 단계마다 최대·최소 곱 후보를 비교해 갱신하고, 전역 최댓값 greatest를 유지합니다.
  4. 모든 순회가 끝나면 greatest를 결과로 반환합니다.

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 상수 공간만 사용하는 O(1)입니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

120

마무리

최대 곱 부분 배열 문제는 카데인 알고리즘(Kadane's Algorithm)을 확장한 대표적인 동적 계획법 문제입니다. 합계 버전과 달리 곱셈에서는 부호 변화 때문에 최솟값까지 함께 추적해야 한다는 점이 핵심입니다. 이 패턴을 익혀 두면 '최대 합 부분 배열', '최대 곱 두 수 찾기' 등 다양한 변형 문제에도 손쉽게 적용할 수 있습니다.