[알고리즘] 연속된 수를 더해서 가장 큰 값 찾기

문제

배열안에 있는 요소중 연속된 num개 만큼 뽑아 더한다. 더한값중 가장 큰값을 찾는 함수만들기

예시 : 

maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);

풀이

(1) 1번 풀이

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^2)

(2) 2번 풀이

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

앞에것만 빼고 뒤에것 더해준다.

시간복잡도 : O(n)