Pagini recente » Cod sursa (job #1819007) | Cod sursa (job #2388574) | Cod sursa (job #1654660) | Cod sursa (job #1920534) | Cod sursa (job #360360)
Cod sursa(job #360360)
#include <fstream>
//#include <iostream>
using namespace std;
int a[5001],sis[5001],pred[5001],n;
void Citire ()
{
ifstream f("subsir2.in");
f>>n;
int i;
for(i=1;i<=n;i++)
f>>a[i];
f.close();
}
int main()
{
int i,k,j,min,poz,min1;
Citire();
sis[n]=1;
pred[n]=n+1;
for(i=n-1;i>=1;i--)
{
min=1000001;
poz=n+1;
sis[i]=n+1;
for(j=i+1;j<=n;j++)
if((a[i]<=a[j])&&(a[j]<=min)&&(sis[i]>sis[j]))
{
pred[i]=j;
min=a[j];
sis[i]=1+sis[j];
}
if(sis[i]==n+1) {sis[i]=1;pred[i]=n+1;}
}
k=1;
for(i=2;i<=n;i++)
if(a[k]>a[i])
k=i;
min=sis[1];poz=1;
min1=a[1];
for(i=2;i<=k;i++)
if((a[i]<min1)&&(min>=sis[i]))
{
poz=i;
min1=a[i];
min=sis[i];
}
ofstream f("subsir2.out");
f<<sis[poz]<<"\n";
k=poz;
while(k<n+1)
{
f<<k<<" ";
k=pred[k];
}
f<<"\n";
f.close();
/*for(i=1;i<=n;i++)
cout<<sis[i]<<" ";
cout<<"\n";
for(i=1;i<=n;i++)
cout<<pred[i]<<" ";
*/
return 0;
}