max_profit_fast.php

<?php
//this is to get the max gap in an array supposing gap can only be a later number minus a former number

$stock_prices_yesterday = [25, 7, 5, 8, 11, 9];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 6 (buying for $5 and selling for $11)
print "1st:the most profit should be 6: {$m_profit}";

$stock_prices_yesterday = [10, 7, 11, 5, 8, 9];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 4 (buying for $7 and selling for $11, or buying for $5 and selling for $9)
print "\n2nd:the most profit should be 4: {$m_profit}";

$stock_prices_yesterday = [10, 7, 11, 5, 8, 7];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 6 (buying for $7 and selling for $11)
print "\n3rd:the most profit should be 4: {$m_profit}";

$stock_prices_yesterday = [10, 7, 9, 5, 8, 7];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 6 (buying for $5 and selling for $8)
print "\n4th:the most profit should be 3: {$m_profit}";

$stock_prices_yesterday = [10, 7, 9, 5, 8, 7];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 6 (buying for $5 and selling for $8)
print "\n5th:the most profit should be 3: {$m_profit}";

$stock_prices_yesterday = [16, 9, 7, 5, 3, 10];
$m_profit = GetMaxProfit($stock_prices_yesterday);
# returns 6 (buying for $3 and selling for $10)
print "\n6th:the most profit should be 7: {$m_profit}";

//this is to test large array and the solution's performance
$ran_prices = range(1, 1000000, 3);
shuffle($ran_prices );

$time_s = microtime(true);
$m_profit = GetMaxProfit($ran_prices);
$time_e = microtime(true);

$td = $time_e - $time_s;
print "\n7th:Testing performance using random large array\nthe most profit is ?: {$m_profit} [Time:{$td}]";


function GetMaxProfit(array $prices): int {
    $currMax = 0;
    $totalMax = 0;
  for($i = 1; $i < count($prices); $i++){
        $currMax = max(0, $currMax + $prices[$i] - $prices[$i-1]);
        $totalMax = max($totalMax, $currMax);
    }
  return $totalMax;
}

The running result:
1st:the most profit should be 6: 6
2nd:the most profit should be 4: 4
3rd:the most profit should be 4: 4
4th:the most profit should be 3: 3
5th:the most profit should be 3: 3
6th:the most profit should be 7: 7
7th:Testing performance using random large array
the most profit is ?: 999990 [Time:0.076534032821655]

The question: https://gist.github.com/jonog/ecd6a02adbe3bd496cefcd63d363c876