Instantly share code, notes, and snippets.

Embed
What would you like to do?
get the max profit of a certain interval
<?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";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment