Нахождение наибольшей подпоследовательности в массиве

[Vladimir2]

Большая просьба, помогите написать на Delphi програмку по такому заданию

Вводится массив. Найти в нем длину самой длинной возрастающей подпоследовательности. Например, в массиве

5 1 4 6 2 10

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

Заранее благодарю.

[Oscar]

1. Отсортировать.
2. Установить счётчик в 0.
3. Проходить по массиву с минимума до максимума
4. Если разница между предидущим элементом и нынешним больше единицы - устанавливать счётчик в 1, иначе инкрементировать счётчик.

Сорри, делфи под рукой нет.

[Vladimir2]

А если без сортировки?

[Oscar]

В задании сказано "без сортировки", или почему нельзя?
Если нужно сохранить исходный массив - его можно просто скопировать перед этим всем.

Если же сортировать действительно нельзя (что меня довольно таки удивляет), то нужно хорошенько задуматься...

[Vladimir2]

Суть такая, через listbox вводится массив "как есть". Необходимо прошерстить введенный массив, найти подпоследоватедьности, найти наибольшую подпоследовательновсть, вывести колличество знаков в ней.

Код: Выделить всё

begin
  count:=0;
  x:=0;
  y:=0;
  for i:=1 to length(mas) do
    if mas[i+1] > mas[i] then
     inc(count)
    else x:=count; count:=0;
      if x > y then y:=x;
    showmessage(inttostr(y));
end;

Такой вариант не правилен, т.к. счетчик срабатывает на начало любой последовательности.

[Oscar]

Код: Выделить всё

<pre>
<?php

$input = array();

$max = 30;
for($i = 0; $i < $max; $i++) {
	$input[$i] = rand(0, $max);
}

$input = array_unique($input);

/*
$input[0] = 5;
$input[1] = 1;
$input[2] = 4;
$input[3] = 6;
$input[4] = 2;
$input[5] = 10;
*/

$longestSequence = 0;


if (count($input) > 0) {

	$temp = $input;

	sort($temp);
	print_r($temp);

	$first = $temp[0];
	$last = $temp[0];

	$tempSequence = 1;
	$longestSequence = 1;

	for($i = 1; $i < count($temp); $i++) {
		if ($first-$temp[$i] == 1) {
			$tempSequence++;
			$first = $temp[$i];
		} else if ($temp[$i] - $last == 1) {
			$tempSequence++;
			$last = $temp[$i];
		} else {

			if ($tempSequence > $longestSequence)
				$longestSequence = $tempSequence;

			$tempSequence = 1;
			$first = $temp[$i];
			$last = $temp[$i];
		}
	}
}

if ($tempSequence > $longestSequence)
	$longestSequence = $tempSequence;

echo "
Longest sequence: $longestSequence\n";

?>
</pre>

Это PHP.

Нужно добавить, что у текущей последовательности есть first и last элементы (проверяемый элемент должен быть на единицу меньше first элемента, или на единицу больше last элемента, только тогда нужно инкрементировать счётчик),

И счётчик нужно иметь отдельно от конечного результата ($tempSequence - счётчик, $longestSequence - конечный результат; когда обнуляется счётчик (устанавливается в единицу), конечный результат равен максимуму между текущим значением и счётчиком; то же самое нужно проделать после цикла, для последней проверяемой последовательности).

Кроме того, первый и последний элементы нужно всегда подправлять.

[Oscar]

Код: Выделить всё

<?php

$input = array();

$input[0] = 5;
$input[1] = 1;
$input[2] = 4;
$input[3] = 6;
$input[4] = 2;
$input[5] = 10;

$longestSequence = 0;

if (count($input) > 0) {

	$temp = $input; // COPY ARRAY (to save real values)

	sort($temp); // ASCENDING SORTING

	$current = $temp[0]; // init current element

	$tempSequence = 1; // temporary counter
	$longestSequence = 1; // result

	for($i = 1; $i < count($temp); $i++) {

		if (abs($current - $temp[$i]) > 1) { // |current - temp| > 1

			if ($tempSequence > $longestSequence)
				$longestSequence = $tempSequence; // result = max(temp, result)

			$tempSequence = 1; // reset counter

		} else {

			$tempSequence++; // increment counter

		}

		$current = $temp[$i]; // update current element

	}
}

if ($tempSequence > $longestSequence)   // result = max(temp, result)
	$longestSequence = $tempSequence; // for the last sequence



echo "
Longest sequence: $longestSequence\n"; // OUTPUT

?>

Прошу прощения, разделение на FIRST и LAST не нужно (это я уже начал было думать о неотсортированном варианте).
Нужно было всего лишь добавить разницу между счётчиком и конечным результатом, являющимся максимумом этих двух значений.