PHP
Дан одномерный массив. Найти максимальную по длине подпоследовательность, элементы которой, в свою очередь, образуют монотонную последовательность (монотонно возрастает или монотонно убывает).
чтото сегодня на составление алгоритмов тянет =)
Код:
<?php
//поиск самой длинной монотонно убывающей последовательности
$arr = array(1,2,3,3,2,1,4,5,6,7,6,5,4);
$seq_arr = array();
$cur_arr = array($arr[0]);
for ($i=1;$i<count($arr);$i++)
{
if ( $cur_arr[count($cur_arr)-1] >= $arr[$i] )
{
array_push($cur_arr, $arr[$i]);
}
else
{
array_push($seq_arr, $cur_arr);
$cur_arr = array($arr[$i]);
}
}
array_push($seq_arr, $cur_arr);
$final_arr = array();
for ($i=1;$i<count($seq_arr);$i++)
{
if (count($final_arr) < count($seq_arr[$i]))
$final_arr = $seq_arr[$i];
}
print_r($final_arr);
?>
<?php
//поиск самой длинной монотонно возрастающей последовательности
$arr = array(1,2,3,3,2,1,4,5,6,7,6,5,4);
$seq_arr = array();
$cur_arr = array($arr[0]);
for ($i=1;$i<count($arr);$i++)
{
if ( $cur_arr[count($cur_arr)-1] <= $arr[$i] )
{
array_push($cur_arr, $arr[$i]);
}
else
{
array_push($seq_arr, $cur_arr);
$cur_arr = array($arr[$i]);
}
}
array_push($seq_arr, $cur_arr);
$final_arr = array();
for ($i=1;$i<count($seq_arr);$i++)
{
if (count($final_arr) < count($seq_arr[$i]))
$final_arr = $seq_arr[$i];
}
print_r($final_arr);
?>
//поиск самой длинной монотонно убывающей последовательности
$arr = array(1,2,3,3,2,1,4,5,6,7,6,5,4);
$seq_arr = array();
$cur_arr = array($arr[0]);
for ($i=1;$i<count($arr);$i++)
{
if ( $cur_arr[count($cur_arr)-1] >= $arr[$i] )
{
array_push($cur_arr, $arr[$i]);
}
else
{
array_push($seq_arr, $cur_arr);
$cur_arr = array($arr[$i]);
}
}
array_push($seq_arr, $cur_arr);
$final_arr = array();
for ($i=1;$i<count($seq_arr);$i++)
{
if (count($final_arr) < count($seq_arr[$i]))
$final_arr = $seq_arr[$i];
}
print_r($final_arr);
?>
<?php
//поиск самой длинной монотонно возрастающей последовательности
$arr = array(1,2,3,3,2,1,4,5,6,7,6,5,4);
$seq_arr = array();
$cur_arr = array($arr[0]);
for ($i=1;$i<count($arr);$i++)
{
if ( $cur_arr[count($cur_arr)-1] <= $arr[$i] )
{
array_push($cur_arr, $arr[$i]);
}
else
{
array_push($seq_arr, $cur_arr);
$cur_arr = array($arr[$i]);
}
}
array_push($seq_arr, $cur_arr);
$final_arr = array();
for ($i=1;$i<count($seq_arr);$i++)
{
if (count($final_arr) < count($seq_arr[$i]))
$final_arr = $seq_arr[$i];
}
print_r($final_arr);
?>