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

Найти ее максимальную возрастающую подпоследовательность - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
IrinaHM
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 3
18.10.2010, 08:07     Найти ее максимальную возрастающую подпоследовательность #1
Здравствуйте, помогите студентке, завтра надо сдать задачи, одна не получается
Дана последовательность целых чисел. Найти ее максимальную
возрастающую подпоследовательность. (Хотя бы одну)
Пример: 8 1 3 2 3 9 4 8 6 -> 1 2 3 4 6
^ ^ ^ ^ ^
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2010, 08:07     Найти ее максимальную возрастающую подпоследовательность
Посмотрите здесь:

C++ найти максимальную по длине подпоследовательность так,чтобы элементы были в возрастающем порядке
Найти самую длинную подпоследовательность, которая является арифметической или геометрической прогрессией C++
Найти самую длинную возрастающую цепочку простых чисел C++
C++ В массиве целых чисел найти максимально длинную возрастающую последовательность
Найти номер элемента из массива А, с которого массив В начинается как подпоследовательность C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
18.10.2010, 08:38     Найти ее максимальную возрастающую подпоследовательность #2
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
max=1;
tempmax=1;
indexmax=0;
for(int i=1,i<n;i++)
{
 if (a[i]<=a[i-1])
 {
  if (tempmax > max)
   {
    max=tempmax;
    indexmax = i - max;
    tempmax=1;
   }
  else
  {
   tempmax++;
  }
 
 }
}
 
for (int i=indexmax;i<indexmax + max -1;i++)
{
  cout<<a[i]<<" ";
}
IrinaHM
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 3
18.10.2010, 09:14  [ТС]     Найти ее максимальную возрастающую подпоследовательность #3
А можно еще комменты написать в модуле?
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
18.10.2010, 10:07     Найти ее максимальную возрастающую подпоследовательность #4
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
max=1;//Максимальная длина последовательности
tempmax=1;//Длина текущей последовательности
indexmax=0;//Номер первого элемента максимальной длины последовательности
for(int i=1,i<n;i++)
{
 if (a[i]<=a[i-1])//Если предыдущий элемент больше или равен следующему, тогда проверяем
 {
  if (tempmax > max) //Если длина текущей последовательности больше максимальной, тогда
   {
    max=tempmax;//максимальной присваем значение текущей
    indexmax = i - max;//находим номер первого элемента этой последовательности
    tempmax=1;//присваиваем минимальное возможное значение текуще последовательности
   }
  else // иначе, то есть если следующий элемент больше предыдущего
  {
   tempmax++;//увеличиваем длину текущей последовательности на 1
  }
 
 }
}
 
for (int i=indexmax;i<indexmax + max -1;i++)//начиная с первого элемента максимальной последовательности, выводим все элементы этой максимальной последовательности
{
  cout<<a[i]<<" ";
}
IrinaHM
0 / 0 / 0
Регистрация: 18.10.2010
Сообщений: 3
19.10.2010, 06:56  [ТС]     Найти ее максимальную возрастающую подпоследовательность #5
Выдает неправильный результат, например в последовательности 7 2 4 4 7 9 выдает 4 4?

Добавлено через 17 часов 36 минут
Помогите исправить, чтобы правильно выбирала... Крик души....
mamedovvms
2913 / 834 / 93
Регистрация: 30.04.2009
Сообщений: 2,613
19.10.2010, 08:22     Найти ее максимальную возрастающую подпоследовательность #6
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
max=1;
tempmax=1;
indexmax=0;
for(int i=1,i<n;i++)
{
 if (a[i]<=a[i-1])
 {
  if (tempmax > max)
   {
    max=tempmax;
    indexmax = i - max;
   }
   tempmax=1;
  }
  else
  {
   tempmax++;
  }
}
 
for (int i=indexmax;i<indexmax + max -1;i++)
{
  cout<<a[i]<<" ";
}
Извините скобочку не там поставил
Yandex
Объявления
19.10.2010, 08:22     Найти ее максимальную возрастающую подпоследовательность
Ответ Создать тему
Опции темы

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