Pagini recente » Cod sursa (job #1810075) | Cod sursa (job #2702717) | Cod sursa (job #1440593) | Cod sursa (job #1349484) | Cod sursa (job #2177405)
#include <cstdio>
using namespace std;
int n,a[100001],best[1000001],pos[1000001],leng;
void Read()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
scanf("%i",&n);
for(int i=0;i<n;i++)
scanf("%i",&a[i]);
}
void Dinamic()
{
pos[n-1] = 0;
best[n-1] = 0;
for(int i=n-2;i>=0;i--)
{
for(int j=i+1;j<=n;j++)
{
if(a[i] < a[j] && best[i] <= best[j])
{
best[i] = best[j] + 1;
pos[i] = j;
}
}
}
}
void Choose(int x)
{
printf("%i\n",leng);
while(leng != 0)
{
printf("%i ",a[x]);
x = pos[x];
leng--;
}
}
int main()
{
int pos;
Read();
Dinamic();
leng=1;
for(int i=n-2;i>=0;i--)
{
if(a[i+1] > a[i] && best[i+1] < best[i])
{
leng++;
pos = i;
}
}
Choose(pos);
return 0;
}