PDA

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



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

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

5 1 4 6 2 10

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

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

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

Vladimir2
19.12.2005, 23:01
А если без сортировки?

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

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

Vladimir2
19.12.2005, 23:18
Суть такая, через 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
19.12.2005, 23:56
<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
20.12.2005, 00:28
<?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 не нужно (это я уже начал было думать о неотсортированном варианте).
Нужно было всего лишь добавить разницу между счётчиком и конечным результатом, являющимся максимумом этих двух значений.