[알고리즘] sliding window

💡 maxSubarraySum

maxSubarraySum 함수는 배열과 정수를 인자로 받는다. 인자로 받은 정수 만큼의 연속한 수를 배열 내에서 더할 때, 가장 큰 숫자를 반환한다.

//시간 복잡도 O(n^2)
function maxSubarraySum(arr, num) {
  if ( num > arr.length){
    return null;
  }
  var max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++){
    temp = 0;
    for (let j = 0; j < num; j++){
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

//시간 복잡도 O(n)
//for문이 두 개이지만 중첩되지 않았기 때문에 더 적은 시간 복잡도가 나온다

function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  
  //맨 처음 인덱스 0부터 num-1 까지의 배열 요소를 더한 것을 maxSum에 할당한다
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  
  //tempSum에 maxSum을 할당하고, for문 내부에서 더하는 범위를 한칸씩 이동시킬 때마다 새로 더하는 게 아니라 
 //이전 인덱스 하나에 해당하는 값을 빼고, 새롭게 더해진 인덱스에 해당하는 값만 더한다. 
  //arr가 [1,2,3,4]이고 num이 3이면
  //tempSum은 1+2+3에서 1+2+3-1+4로 바뀌는 것 
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}