Одномерный массив(самая длинная возрастающая последовательность)

Question

Сама задача звучит так: Найти максимально длинную возрастающую последовательность. Элементы не обязательно должны идти последовательно. E.g.: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} --> {2, 4, 6, 8} Сам сидел думал дня 3 и ничего дельного в голову не идёт подскажите как делать такое может подход какой есть чтобы подступиться к задаче, а я ни сном ни духом.

Answer 1

Ну есть решение на c++ вот

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
  int n;
  cin >> n;
  int mas[1000];
  for(int i = 0; i < n; i++)
    cin >> mas[i];
    int count[1000];
  count[0] = 1;
 
  for(int  i = 1; i < n; i++){
        count[i] = 1;
        for(int j = 0; j < i; j++){
            if(mas[i] > mas[j] && count[j] + 1 > count[i])
                count[i] ++;
        }
  }
  sort(count, count + n);
  cout << count[n - 1];
    return 0;
    }

Создаём массив для длин подпоследовательностей и заполняем его 1.
Пробегаемся по массиву с последовательностью со второго элемента и ищем элемент меньше него с максимальным значением во втором массиве, прибавляем к этому значению 1 и записываем во второй массив. 3)Выводим максимальное значение из второго массива.

Answer 2

Первым алгоритмом мы заполняем массив mas[], потом создаем массив arr[] первый элемент которого равен единице, а остальные равны нулю. Потом опять идет цикл for(int i)который начинается с 1 и до конца, в нем есть еще один цикл for(int j) который идет с самого начала и до i. В нем мы проверяем если i-элемент, больше j-элемента, то во второй массив на j позицию добавляем единицу. Во время цикла запоминаем лучший результат и выводим его.

Answer 3

Можно вот такой вариант решения рассмотреть.

int[] array = new int[] { 9, 6, 2, 7, 4, 7, 6, 5, 8, 4 };
List<int> result = new List<int>();
for (int i = 0; i < array.Length - 1; i++)
{
    List<int> list = new List<int> { array[i] };
    for (int j = i + 1; j < array.Length; j++)
    {
        if (array[j] < list[list.Count - 1] && (list.Count == 1 || array[j] > list[list.Count - 2]))
            list[list.Count - 1] = array[j];
        else if (array[j] > list[list.Count - 1])
            list.Add(array[j]);
    }
    if (result.Count < list.Count)
        result = list;
}
Console.WriteLine(string.Join(", ", result));

Вывод в консоль

2, 4, 5, 8

Это конечно не 2, 4, 6, 8, как в вопросе, но думаю, что так же удовлетворяет условию задачи.

БЛОГ НА HUSL

Одномерный массив(самая длинная возрастающая последовательность)

Ответы (3 шт):