Максимально длинная последовательность

@Mayonez · Регистрация: 26.12.2009

Студворк — интернет-сервис помощи студентам

дан масив чисел до 1 000 000 чисел
нужно выбрать максимально длинную последовательность возрастающих чисел и вывести её на экран
момню, была похожая задачка, но не могу найти
помогите, очень нужно

silent_1991 · 26.10.2010, 17:01

В чём проблема? У вас есть идеи решения?

@Mayonez · 26.10.2010, 17:44 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main()
{
    vector<int> m; // последовательность
    int n; // её длина
    ... // считываем последовательность
 
    vector<int> a (n, 1); // таблица длин
    a[0] = 1;
    vector<int> pred (n, -1); // таблица предков, если надо вывести и саму подпоследовательность
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            if (m[j] < m[i])
                if (a[j]+1 > a[i])
                {
                    a[i] = a[j]+1;
                    pred[i] = j;
                }
    
    // выводим длину последовательности
    cout << * max_element (a.begin(), a.end());
 
    // ищем и выводим саму подпоследовательность
    vector<int> result;
    for (int cur = int (max_element (a.begin(), a.end()) - a.begin()); cur != -1; cur = pred[cur])
        result.push_back (m[cur]);
    cout << endl;
    for (unsigned i=result.size(); i-- > 0; )
        cout << result[i] << ' ';
}

нашёл

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874

	Максимально длинная последовательность 26.10.2010, 15:59. Показов 2170. Ответов 2 Метки нет (Все метки) дан масив чисел до 1 000 000 чисел нужно выбрать максимально длинную последовательность возрастающих чисел и вывести её на экран момню, была похожая задачка, но не могу найти помогите, очень нужно 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	26.10.2010, 17:01
	В чём проблема? У вас есть идеи решения? 0

Максимально длинная последовательность

Решение