Sliding Window 알고리즘

일정한 범위를 가지고 있는 것을 유지하면서 이동하는 것.

/*
문제
	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, 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
console.log(maxSubarraySum_([2, 3, 1, 7, 2, 2, 9, 1, 3, 5, 2, 3, 4, 5, 6], 4)); // 20

핵심 아이디어

• 사실 수열의 길이만큼 이동하면서 연속된 수열의 첫 번째 값과, 수열의 마지막 항에 들어오게 될 새로운 값을 비교하는 아이디어가 sliding window 알고리즘의 핵심이다.
• 별로 놀랍지 않은 아이디어이다.
• tempSum을 계속 갱신 시켜주는 것이 핵심이라고 생각이든다.
• 처음에 비슷한 알고리즘으로 코드를 구현했는데, tempSum을 계속 들고다닌 다는 생각을 못했다.
• 배열의 길이와 상관없이 한 번만 배열을 순회하므로, O(N)이다!