问题描述
给定一个长为n的序列，求它的最长上升子序列的长度和一种方案。
输入格式
输入第一行包含一个整数n。
第二行包含n个整数，为给定的序列。
输出格式
输出的第一行包含一个非负整数，表示最长上升子序列的长度。
第二行包含多个整数，为最长上升子序列中的元素对应的下标 ，按下标从小到大的顺序输出。
样例输入
5
1 3 2 5 4
样例输出
3
1 3 4
样例输入
5
8 5 7 9 1
样例输出
3
2 3 4
数据规模和约定
0<n<=1000，每个数不超过10^6。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[3005];
int dp[3005]={0};
void DPandoutput()
{
int maxz = 0, s[1005];
int posdp,pos=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j])
{
dp[i]=max(dp[j]+1,dp[i]);
if(dp[i]>=maxz)
pos=i;
maxz=max(maxz,dp[i]);
}
}
}
printf("%d\n",maxz);
posdp=maxz;
s[1]=a[pos];
int count=1;
for(int i=pos-1;i>=1;i--){
if(dp[i]==posdp-1)
{
s[++count]=a[i];
posdp=dp[i];
}
}
for(int i=count;i>=1;i--)
for (int j = n; j >= 1; j--)
if (s[i] == a[j]) printf("%d ",j);
printf("\n");
return;
}
int main()
{
DPandoutput();
return 0;
}
除样例外又测了多组数据，输出都正确，求各位帮本蒟蒻看看程序有什么问题，谢谢！
