Pagini recente » Cod sursa (job #167251) | Cod sursa (job #2127301) | Cod sursa (job #2894422) | Cod sursa (job #529236) | Cod sursa (job #3177692)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
vector<int> v,b;
int n,x,rez,lp;
int longestIncreasingSubsequence(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int max_length=0;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
if(max_length<dp[i])
{
max_length=dp[i];
lp=i;
}
}
}
}
// int max_length = *max_element(dp.begin(), dp.end());
return max_length;
}
int main() {
fin>>n;
for(int i=1;i<=n;i++){
fin>>x;
v.push_back(x);
}
rez=longestIncreasingSubsequence(v);
fout<<rez<<'\n';
int c=rez;
while(rez!=0){
if(v[lp+1]>v[lp]){
b.push_back(v[lp]);
// fout<<v[lp]<<" "<<v[lp-1]<<" "<<rez<<'\n';
rez--;
//fout<<rez<<" ";
}
lp--;
}
for(int i=c-1;i>=0;i--)
fout<<b[i]<<" ";
return 0;
}