Sliding Window是在一筆連續資料中,比對加總值最大/最小的一個演算法

const maxSum = (arr, size) => {
    if (size > arr.length) return null;
    let firstIndex = 0;
    const lastIndex = arr.length - size;
    let result = 0;
    for (let i = firstIndex; i <= lastIndex; i++) {
        let amount = 0;
        for (let times = i; times < size + i; times++) {
            amount += arr[times];
        }
        // maxSum
        result = result <= amount ? amount : result;
    }
    return result;
};

console.log(maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3)); // 12

使用兩個for loop比對,先取出第一個值,之後的每次循環都比對上一次的直,保留最大/最小值…,直覺地寫出O(n^2)

// improved
// 算出每個累加size的大小，在和下一個比較(size + 1再減去第一筆)
const improvedMaxSum = (arr, size) => {
    if (size > arr.length) return null;
    let resultValue = 0;
    for (let i = 0; i < size; i++) {
				// 處理第一筆累加
        resultValue += arr[i];
    }
		// 存取第一次loop加總結果
    let currentValue = resultValue;
    for (let i = size; i < arr.length; i++) {
        // arr[i]為當前加總下一筆值
        // arr[i - size]為當前加總需扣除的第一筆值
        // currentValue每個loop都會被更新
        currentValue = currentValue + arr[i] - arr[i - size];
        if (currentValue > resultValue) resultValue = currentValue;
    }
    return resultValue;
};

console.log(improvedMaxSum([2, 7, 3, 0, 6, 1, 5, 12, 11], 3)); // 28