maxSubArray 문제풀이

내 풀이

/*
문제
	Write a function called maxSubarraySum which accepts
	an array of integers and a number called n. The function
	should calculate the maximum sum of n consecutive
	elements in the array.
*/

function maxSubarraySum(arr, n) {
    if (arr.length < n) {
        return null;
    }
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += arr[i];
    }
    for (let i = 1; i <= arr.length - n; i++) {
        let tmp = 0;
        for (let j = i; j < i + n; j++) {
					tmp += arr[j];
				}
				if (sum < tmp){
					sum = tmp;
				}
    }

    return sum;
}

console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2)); // 10
console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(maxSubarraySum([4, 2, 1, 6], 1)); // 6
console.log(maxSubarraySum([4, 2, 1, 6, 2], 4)); // 13
console.log(maxSubarraySum([], 4)); // null

설명

• 아이디어가 안떠올라서 일단 O(N^2)으로 풀었다.
• 풀이방식은 이중 for문을 이용해서 모든 합을 비교하여 가장 큰 값을 찾았다.

시행착오

• 처음에 for문 한번만 써서 풀고싶었기에, idx를 갱신해주면서 풀이하려고 했다.

let idx = 0;
for (let i = n; i <= arr.length; i++) {
  if (arr[idx] < arr[i]){
	sum = sum + arr[idx++] - arr[i]
  }
}

• 이렇게 풀게되면, if 문에 걸리지않았을 때 연속된 수열이아닌 값이 sum으로 되는 경우가 발생한다.

정답 풀이

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;
}

console.log(maxSubarraySum_([1, 2, 5, 2, 8, 1, 5], 2)); // 10
console.log(maxSubarraySum_([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(maxSubarraySum_([4, 2, 1, 6], 1)); // 6
console.log(maxSubarraySum_([4, 2, 1, 6, 2], 4)); // 13
console.log(maxSubarraySum_([], 4)); // null

Sliding Window Algorithm

• 정답 풀이 방식이 이 알고리즘을 사용한 것인데, 시간복잡도가 O(N)으로 굉장히 유용하다.
  = 범위를 가지고 유지하면서 이동하는 알고리즘인데 새로운 포스트에서 따로 다루는 것이 나을 것같다.