Categories
General

How to window sliding ? How to find the greatest sum of 4 elements in array ?

<?php 
function maxSum( $arr, $n, $k)
{
    // n must be greater
    if ($n < $k)
    {
        echo "Invalid";
        return -1;
    }
 
    // Compute sum of first
    // window of size k
    $max_sum = 0;
    for($i = 0; $i < $k; $i++)
    $max_sum += $arr[$i];
 
    // Compute sums of remaining windows by
    // removing first element of previous
    // window and adding last element of
    // current window.
    $window_sum = $max_sum;
    for ($i = $k; $i < $n; $i++)
    {
        echo "(window_sum) $window_sum \n\r";
        $window_sum += $arr[$i] - $arr[$i - $k];
        echo "(arr[$i])". $arr[$i]." - (arr[$i - $k])".$arr[$i - $k]."\n\r";
        echo "$i (window_sum) $window_sum \n\r";
        
        $max_sum = max($max_sum, $window_sum);
    }
 
    return $max_sum;
}
 
    // Driver code
    $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20);
    $k = 4;
    $n = count($arr);
    echo maxSum($arr, $n, $k);
 
// This code is contributed by anuj_67

Leave a Reply