[Javascript 알고리즘] 연속된 부분 배열의 최대 합

문제

정수 배열과 윈도우 크기 k가 주어졌을 때, 연속된 k개의 원소의 합 중 최대값을 찾는 함수를 작성해주세요.

풀이 접근

• 잘 몰르겠어서 클로드랑 차근히 풀고 나니 이해가 되었다..
• 첫번째 묶음의 합을 구한다.
• 그 합을 최대값으로 저장한다.
• 한칸씩 이동하면서 최대값을 갱신한다.
• 이때 한칸씩 이동하는 방법: 합에서 이전 묶음의 첫번째 요소를 빼고, 이번묶음의 마지막 요소를 합에 더한다.

풀이

function maxSumSubarray(arr, k) {
  let sum = 0;
  // 1. 첫번째 합을 구한다.
  for (let i = 0; i < k; i++) {
    sum += arr[i];
  }

  // 2. 최대값을 저장한다
  let max = sum;

  // 3. 한칸씩 이동하면서 합을 계산 후 최대값 을 갱신
  for (let i = k; i < arr.length; i++) {
    //합 = 합 - 첫번째 요소 + 다음 요소
    sum = sum - arr[i - k] + arr[i];

    // 맥스 계산
    max = Math.max(max, sum);
  }

  return max;
}

다른 사람 풀이

function maxSumSubarray(arr, k) {
  // 최대값을 저장할 변수
  let maxSum = 0;

  // 배열을 처음부터 끝까지 순회
  for (let i = 0; i <= arr.length - k; i++) {
    let sum = 0;

    // 현재 위치부터 k개의 숫자를 더함
    for (let j = i; j < i + k; j++) {
      sum += arr[j];
    }

    // 최대값 갱신
    if (sum > maxSum) {
      maxSum = sum;
    }
  }

  return maxSum;
}

배운 점

다른 풀이는 완전탐색(브루트포스) 방식으로 푸는 방법이라고 한다.
이중 반복문을 해서 풀수 있다. 이중 반복문의 조건부가 항상 헷갈린다..