1 solutions

  • -1
    @ 2024-7-10 10:15:47
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int f[N],a[N],g[N];
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)cin>>a[i];
    	for(int i=1;i<=n;i++)
    	{
    		f[i]=1;
    		for(int j=1;j<i;j++)
    		{
    			if(a[i]>=a[j]&&f[i]<f[j]+1)
    			{
    				f[i]=f[j]+1;
    				g[i]=j;
    			}
    		}
    	}
    	int maxv=0,index;
    	for(int i=1;i<=n;i++)
    	{
    		if(f[i]>maxv)
    		{
    			maxv=f[i];
    			index=i;
    		}
    	}
    	cout<<"max="<<maxv<<endl;
    	stack<int> stk;
    	while(index)
    	{
    		stk.push(a[index]);
    		index=g[index];
    	}
    	while(stk.size())
    	{
    		cout<<stk.top()<<" ";
    		stk.pop();
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    980
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    (None)
    # Submissions
    23
    Accepted
    7
    Uploaded By