“Алгоритм скользящего окна JavaScript” Ответ

Алгоритм скользящего окна JavaScript

Here is an example.

Input Array: [2, 6, 9, 2, 1, 8, 5, 6, 3]

num: 3

//Let’s define two variables tracking sums of the consequent subset and the maximum sum compared to the temporary sum.

function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
}

//2. If the length of an array is less than the num, we should return null before start looping through the array.

function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
}

//3. Start looping through an array from index 0 to the size of num, and add every element to the tempSum

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

//4. Set the tempSum to the maxSum variable, and loop through the array again starting from the num to get a new tempSum. The new tempSum is achieved by sliding window of the array so we can subtract the previous element of the new subset and add the new element

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

//5. Now, it’s time to compare between maxSum and tempSum and set bigger sum as maxSum, in which we will return at last.

function maxSumArr(arr, num) {
    let maxSum = 0;
    let tempSum = 0;
    if(arr.length < num) return null;
    for(let i = 0; i < num; i++) {
       tempSum += arr[i];
    }
    tempSum = maxSum;
    for(let i = num; i < arr.length; i++) {
       tempSum = tempSum - arr[i - num] + arr[i];
       maxSum = Math.max(tempSum, maxSum);
       }      
       return maxSum;
}
//We got our sum of the maximal subarray! Using the Sliding Window algorithms, it reduced the operating time to O(n). Great job.