最长不下降子序列

绝地灬酷狼 2022-06-16 13:45 231阅读 0赞

/*开辟一个堆栈数组stack[]，每次取栈顶元素top和读到的元素temp做比较，
    如果temp>top则将temp入栈，如果temp<=top则二分查找栈中的比temp大的第一个元素，
    并用temp替换他，最后max即为栈的大小 
     */ 
    #include <iostream>
    #include <cstdlib>
    #define SIZE 1001
    using namespace std;
     
    int main()
    {
      int i, j, n, top, temp;
      int stack[SIZE];
      cin >> n;
      top = 0;
      stack[0] = -1;//第一个元素可能为0
      for (i = 0; i < n; i++)
      {
        cin >> temp;
        if (temp > stack[top])//比栈顶元素大数就入栈
          stack[++top] = temp;
        else
        {
          int low = 1, high = top;
          int mid;
          while(low <= high)//二分检索栈中比temp大的第一个数
          {
            mid = (low + high) / 2;
            if (temp > stack[mid])
              low = mid + 1;
            else
              high = mid - 1;
          }
          stack[low] = temp;//用temp替换
        }
      }
      cout << top << endl;//最长序列数就是栈的大小
      return 0;
    }

//动态规划 
    #include<iostream>
    using namespace std;
    int a[10001];
    int Link[10001]; 
    int Long[10001];
    int n,Max;
    
    int find(int key)
    {
    	int L=1,R=Max,mid;
    	while(L<=R)
    	{
    		mid=(L+R)/2;
    		if(a[Long[mid]]<key)
    			L=mid+1;
    		else R=mid-1;
    	}
    	return L-1;
    }
    
    int main()
    {
    	int i,j,k,l;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    	}
    	Max=1;
    	Long[Max]=1;
    	Link[1]=1;
    	for(i=2;i<=n;i++)
    	{
    		if(a[i]>=a[Long[Max]])
    		{
    			Max++;
    			Long[Max]=i;
    			Link[i]=Long[Max-1];
    		}
    		else
    		{
    			l=find(a[i]);
    			Long[l+1]=i;
    			Link[i]=Long[l];
    		}
    	}
    	cout<<Max<<endl;
    	k=Max;
    	i=Long[Max];
    	while(Max>0)
    	{
    		Long[Max]=a[i];
    		i=Link[i];
    		Max--;
    	}
    }

#include<iostream>
    using namespace std;
    int n,longest;
    int a[10001],dp[10001];
    int main()
    {
    	cin>>n;
    	longest=1;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		dp[i]=1;
    	}
    	for(int i=2;i<=n;i++)
    	{
    		for(int j=1;j<i;j++)
    		{
    			if(a[i]>a[j]) dp[i]=max(dp[j]+1,dp[i]);
    		}
    		longest = max(dp[i],longest);
    	}
    	cout<<longest<<endl;
    }