programming/max_sub_array_of_size_k.js at main · dpwanjala/programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// brute-force algorithm
// function max_sub_array_of_size_k(k, arr) {
//     let maxSum = 0,
//         windowSum = 0;

//     for (i = 0; i < arr.length - k + 1; i++) {
//         windowSum = 0;
//         for (j = i; j < i + k; j++) {
//             windowSum += arr[j];
//         }
//         maxSum = Math.max(maxSum, windowSum);
//     }
//     return maxSum;
// }


// console.log(
//     `Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2])}`);
// console.log(
//     `Maximum sum of a subarray of size K: ${max_sub_array_of_size_k(2, [2, 3, 4, 1, 5])}`);


// sliding window pattern algorithm
function max_sub_array_of_size_k(k, arr) {
    let maxSum = 0,
        windowSum = 0,
        windowStart = 0;

    for (window_end = 0; window_end < arr.length; window_end++) {
        windowSum += arr[window_end]; // add the next element
        // slide the window, no need to slide if we've not hit the window size of 'k'
        if (window_end >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[windowStart]; // subtract the element going out
            windowStart += 1; // slide the window ahead
        }
    }
    return maxSum;
}


console.log(`Maximum sum of a subarray of size K: `
    + max_sub_array_of_size_k(3, [2, 1, 5, 1, 3, 2]));
console.log(`Maximum sum of a subarray of size K: `
    + max_sub_array_of_size_k(2, [2, 3, 4, 1, 5]));