PHP самая длинная возрастающая подпоследовательность

Question

Так что здесь есть ответы, которые применимы к C, но я пытаюсь сделать это на PHP, И определенным образом.

У меня есть массив чисел, как это:

7, 2, 6, 3, 10

Я хочу найти самую длинную возрастающую подпоследовательность, которая происходит ПЕРВЫЙ в указанном порядке. Так, например, в этом случае я хочу, чтобы результат был:

2, 6, 10

И НЕ 2, 3, 10.

Каков наилучший способ сделать это?

Answer 1

Вот мое собственное решение самой длинной задачи кодирования возрастающей подпоследовательности, оно прошло все 10 тестовых случаев.

      <?php 

function ArrayChallenge($arr) {

  $newArr = [];
  foreach ($arr as $key => $value) {
    $temp = array_slice($arr, $key, count($arr)-$key);
    //print_r($temp);
    $newArr[$key][] = "";
    for($i=0; $i<count($temp); $i++) {
      if ($temp[$i] > $value && max($newArr[$key]) < $temp[$i]){
        $newArr[$key][] = $temp[$i];
      }
    }
  }
  //print_r($newArr);
  $result = 0;
  foreach ($newArr as $item) {
    if (count($item) > $result) $result = count($item);
  }
  return $result;

}

Answer 2

Хорошо, вот решение вашего вопроса, дающее ожидаемый ответ. По сути, для каждого найденного элемента начинайте список и добавляйте в него элементы, если они больше, чем последний элемент в списке.

$input = array(7,2,6,3,10);
$trial = array();

echo "Input: ";
print_r($input);
echo "<br><br>\n";

foreach ($input as $key => $value)
{
  // Create a new trial for each starting point
  // ------------------------------------------
  $trial[$key][0] = $value;
  echo "Trial $key started<br>\n";

  // Process all prior trials
  // ------------------------
  for ($i = $key-1; $i >= 0; $i--)
  {
    echo "Looking at trial $i ";
    $last = count($trial[$i]) - 1;
    $lastval = $trial[$i][$last];
    if ( $value > $lastval )
    {
      $trial[$i][] = $value;
      echo "** added $value";
    }
    echo "<br>\n";
  }
  echo "<br>\n";
}

// Find first longest trial
// ------------------------
$longest = 0;
foreach ($trial as $key => $list)
{
  if ( count($list) > count($trial[$longest]) )
    $longest = $key;
}

echo "All trials:<br>\n";
print_r($trial);
echo "<br><br>\n";

echo "First longest sequence:<br>\n";
print_r($trial[$longest]);

Конечно, есть вещи, которые можно сделать по-другому, если у вас есть очень большие наборы данных. Тем не менее, вот некоторые "отладочные" выходные данные, показывающие его в действии:

Input: Array ( [0] => 7 [1] => 2 [2] => 6 [3] => 3 [4] => 10 ) 

Trial 0 started

Trial 1 started
... looking at trial 0 

Trial 2 started
... looking at trial 1 ** added 6
... looking at trial 0 

Trial 3 started
... looking at trial 2 
... looking at trial 1 
... looking at trial 0 

Trial 4 started
... looking at trial 3 ** added 10
... looking at trial 2 ** added 10
... looking at trial 1 ** added 10
... looking at trial 0 ** added 10

All trials:
Array ( 
  [0] => Array ( [0] => 7 [1] => 10 ) 
  [1] => Array ( [0] => 2 [1] => 6 [2] => 10 ) 
  [2] => Array ( [0] => 6 [1] => 10 ) 
  [3] => Array ( [0] => 3 [1] => 10 ) 
  [4] => Array ( [0] => 10 ) 
) 

First longest sequence:
Array ( [0] => 2 [1] => 6 [2] => 10 )

Answer 3

Попробуйте этот код

<?php

$data = array(7, 2, 6, 3, 10);
$slice_array=array_slice($data,array_search(min($data),$data));
$result=array();

for($i=array_search(min($slice_array),$slice_array);$i<=array_search(max($slice_array),$slice_array);$i++){
     if(end($result)<$slice_array[$i]){
         array_push($result,$slice_array[$i]);
     }
}
print_r($result);
 ?>

ВЫХОД

Array ( [0] => 2 [1] => 6 [2] => 10 )