get the max profit of a certain interval

max-profit-of-an-interval.php

<?php

$data = array();

for($i = 0; $i <= 50; $i++){
    if(0 == $i){
        $data[] = mt_rand(1,20);
    }else{
        $data[] = max(0, mt_rand($data[$i-1] - 1, $data[$i-1] +1));
    }
}


time_chart($data);

max_profit($data);

function max_profit($data){
    $origin_data = $data;
    arsort($data);
    reset($data);
    $max_key = key($data);
    $max_value = $data[$max_key];
    end($data);
    $min_key = key($data);
    $min_value = $data[$min_key];
    //echo "$min_key: $min_value\t$max_key: $max_value\n";
    if($min_key < $max_key){
        $max_profit = $data[$max_key] - $data[$min_key];
        echo "lucky\n";
        echo "Buy date: $min_key\t Sell date: $max_key\tMax profit: $max_profit\n";
    }else{
        echo "not lucky\n";
        list($buy, $sell, $max_profit) = not_lucky_force($origin_data);
        $buy_value = $data[$buy];
        $sell_value = $data[$sell];
        echo "force: Buy date: $buy-$buy_value\t Sell date: $sell-$sell_value\tMax profit: $max_profit\n\n\n";
        $step = 0;
        $max_profit = not_lucky_optimised($origin_data,  $step);
        echo "step: $step\n";
        echo "max profit: $max_profit\n";
    }
}

function not_lucky_optimised($data, &$step){
    $step++;
    //print_r($data);
    $sorted_data = $data;
    arsort($sorted_data);
    reset($sorted_data);
    $max_key = key($sorted_data);
    end($sorted_data);
    $min_key = key($sorted_data);
    //echo "$min_key\t$max_key\n";
    if($min_key < $max_key){
        return $data[$max_key] - $data[$min_key];
    }
    reset($data);
    $first_key = key($data);
    $first = array_slice($data, 0, $max_key + 1 - $first_key, TRUE);
    $middle = array_slice($data, $max_key + 1 - $first_key,
        $min_key - $max_key - 1, TRUE);
    if(count($middle) <= 2){
        $first = array_shift($middle);
        $second = array_shift($middle);
        $middle_max_profit =  max(0, $second - $first);
    }else{
        $middle_max_profit = not_lucky_optimised($middle, $step);
    }
    $last = array_slice($data, $min_key - $first_key, null, TRUE);
    if(count($first) <= 1){
        $first_max_profit = 0;
    }else{
        $first_max_profit = max($first) - min($first);
    }
    if(count($last) <= 1){
        $last_max_profit = 0;
    }else{
        $last_max_profit = max($last) - min($last);
    }
    return max(
        $first_max_profit,
        $last_max_profit,
        $middle_max_profit
    );
}

function not_lucky_force($data){
    $step = 0;
    $max_profit = 0;
    $max_key = 0;
    $min_key = 0;
    $length = count($data);
    foreach($data as $k => $v){
        for($i = $k+1; $i < $length; $i++){
            $step++;
            if($data[$i] - $data[$k] > $max_profit){
                $max_profit = $data[$i] - $data[$k];
                $max_key = $i;
                $min_key = $k;
            }
        }
    }
    echo "step: $step\n";
    return array($min_key, $max_key, $max_profit);
}

function time_chart($data){
    $flip_data = array();
    $max = max($data);
    $length = count($data);

    foreach($data as $k => $v){
        if(isset($flip_data[$v])){
            if(!is_array($flip_data[$v])){
                $flip_data[$v] = array($flip_data[$v]);
            }
            $flip_data[$v] = array_merge($flip_data[$v], array($k));
        }else{
            $flip_data[$v] = array($k);
        }
    }

    for($i = $max; $i >= 0; $i--){
        $data = isset($flip_data[$i]) ? $flip_data[$i] : array();
        echo "$i";
        for($j = 0; $j < $length; $j++){
            if(in_array($j, $data)){
                echo '.';
            }else{
                echo ' ';
            }
        }
        echo "\n";
    }

}