Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
26.10.2010, 15:59     Максимально длинная последовательность #1
дан масив чисел до 1 000 000 чисел
нужно выбрать максимально длинную последовательность возрастающих чисел и вывести её на экран
момню, была похожая задачка, но не могу найти
помогите, очень нужно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2010, 15:59     Максимально длинная последовательность
Посмотрите здесь:

Найти номер строки, в которой находится самая длинная последовательность C++
C++ В массиве целых чисел найти максимально длинную возрастающую последовательность
Самая длинная последовательность не повторяющихся элементов в массиве C++
Найти сумму максимально отрицательного и максимально положительного элемента массива C++
Массив: Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей. C++
C++ Найти номер элемента, с которого начинается самая длинная последовательность единиц
Если последовательность отсортирована по возрастанию, оставить ее без изменения. Иначе получить иную последовательность C++
C++ Добыть максимально длинную прогрессирующую последовательность

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.10.2010, 17:01     Максимально длинная последовательность #2
В чём проблема? У вас есть идеи решения?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
26.10.2010, 17:44  [ТС]     Максимально длинная последовательность #3
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] << ' ';
}
нашёл
Yandex
Объявления
26.10.2010, 17:44     Максимально длинная последовательность
Ответ Создать тему
Опции темы

Текущее время: 21:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru