Решение задачи Возрастающая подпоследовательность с Меньшиков

Без пояснения   Просмотров: 70


Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.


Код

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> mas,len,res;
void input()
{
    cin>>n;
    mas.resize(n);
    len.resize(n);
    for (int i=0;i<n;i++)
        scanf("%d",&mas[i]);
}
void output()
{
    cout<<res.size()<<endl;
    for (int i=0;i<res.size();i++)
        printf("%d ",res[i]);
}
// сложность O(N*N/2)
void MaxIncSubSeq(vector<int> &mas, vector<int> &res)
{
    // формирование массива len
    for (int i=0;i<n;i++)
    {
        int maxLen = 0;
        for (int j=i-1;j>=0;j--)
            if (mas[j]<mas[i] && len[j]>maxLen)
                maxLen = len[j];
        len[i] = maxLen + 1;
    }
    vector<int>::iterator ItPos = max_element(len.begin(),len.end());
    int lastPos = ItPos - len.begin();
 
    int amount = len[lastPos];
      // формирование ответа
    res.resize(amount);
    int pos = amount-1;
    for (int i=lastPos;i>=0;i--)
        if (len[i]==amount)
        {
            res[pos--] = mas[i];
            amount--;
        }
}
int main()
{
    input();
    MaxIncSubSeq(mas,res);
    output();
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться