1 Востаннє редагувалося Betterthanyou (17.12.2014 20:14:43)

Тема: Завдання

Завдання
Задано послідовність, потрібно знайти довжину найбільшої зростаючої підпослідовності.
Технічні умови
У першому рядку записано довжину n (1 ≤ n ≤ 1000) послідовності. У другому рядку записано
саму послідовність. Числа послідовності - цілі числа, які не перевищують 10000 за модулем.
Вивести найбільшу довжину зростаючої підпослідовності

Що я нічого з цього не зрозумів, підскажіть як це робити ?

2 Востаннє редагувалося koala (15.12.2014 00:00:57)

Re: Завдання

Підпослідовність, що зростає - що щось типу
13 3 5 8 34 3449 23 (виділена частина, що зростає)
13 і 23 теж можна вважати підпослідовностями, що зростають, з 1 елементу кожна.

Подякували: Betterthanyou1

3

Re: Завдання

Ну я так подумав n=7 а послідовність 1 2 3 4 67 68 100 то мені потрібно вивести 1 2 3 4 так ?

4

Re: Завдання

Ні, у вас вся послідовність зростає. Пояснюю ще раз:
13 > 3 < 5 < 8 < 34 < 3449 > 23
Там, де є ланцюжок знаків < - послідовність зростає.
А вивести треба довжину, у вашому випадку - 7, в моєму - 5.

Подякували: Betterthanyou1

5

Re: Завдання

Дякую, тепер зрозумів

6

Re: Завдання

На майбутнє - може ще бути неспадна послідовність, це коли знак ≤. Ну і спадна і незростаюча послідовності - теж зрозуміло, сподіваюся. А загальна назва таких послідовностей - монотонні (зростаюча і спадна звуться строго монотонними).

7 Востаннє редагувалося Betterthanyou (17.12.2014 20:21:43)

Re: Завдання

.

8

Re: Завдання

А нащо всі ці масиви?

int length = 1, max = 1, n, old, element;
cin >> n;
cin >> old;
while( --n )
{
  cin >> element;
  if( element > old )
    ++length;
  else
  {
    if( length > max )
      max = length;
    length = 1;
  }
  old = element;
}
cout << max;
Подякували: Betterthanyou2