max subarray sum

max-subarray-sum.php

<?php
//
// approach
// for any array A0, A1,.. Ai-1, Ai, Ai+1, ... An
// 
// to find max sum up to Ai, life is very easy if we already know 
// max sum up to A[i-1], in particular, max sum up to Ai is :
//
// bigger value among (
//    MaxSum(A0,A1,..An-1) + Ai,    // continue adding Ai to the current sum
//    Ai                            // or we start a new sum
// )
//
// we will need storage of n elements for "max sum up to p-th item", with
// the first item always equal to A0
//
// MS[0] = A0
//
// subsequently, as discussed above:
//
// MS[1] = max(MS[0] + A1, A1)
// MS[2] = max(MS[1] + A2, A2)
// MS[3] = max(MS[3] + A3, A3)
// 
// etc
//
// so we can do this by only one loop, i.e. O(n) time
//
function max_sum_subarray($a) {
    $ms = [ $a[0] ];
    
    for ($i = 1; $i < count($a); ++$i) {
        $ms[$i] = max($ms[$i - 1] + $a[$i], $a[$i]);
    }   
    return max($ms);
}

function max_sum_subarray_ex($a) {
    $ms = [ [ "sum" => $a[0], "start" => 0, "end" => 0] ];

    $current_biggest_sum = $ms[0]["sum"];
    $current_start = 0;
    $current_end = 0;
    
    for ($i = 1; $i < count($a); ++$i) {
        $continue_adding = $ms[$i - 1]["sum"] + $a[$i];
        $start_new_sum = $a[$i];

        if ($continue_adding > $start_new_sum) {
            $start_idx = $ms[$i - 1]["start"];
            $ms[$i] = ["sum" => $continue_adding, "start" => $start_idx, "end" => $i];
        }
        else {
            $ms[$i] = ["sum" => $a[$i], "start" => $i, "end" => $i];
        }
        if ($ms[$i]["sum"] > $current_biggest_sum) {
            $current_biggest_sum = $ms[$i]["sum"];
            $current_start = $ms[$i]["start"];
            $current_end= $ms[$i]["end"];
                
        }
    }   
    return ["sum" => $current_biggest_sum, "start" => $current_start, "end" => $current_end];
}
print_r( max_sum_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) );
print_r( max_sum_subarray_ex([-2, 1, -3, 4, -1, 2, 1, -5, 4]) );