longest ordered subsequence.cpp1.cpp

本问题是计算最长有序子序列的一个动态规划算法,效率为31MS.

#include<iostream>
using namespace std;
int main()
{
     int n;
     cin>>n;
     int * m=new int [n], * w=new int [n];
     for(int j=0;j<=n-1;j++)
     cin>>w[j];
     m[0]=1;
     int b=1;
     for(int i=1;i<=n-1;i++)
     { 
             m[i]=1;
             for(int k=0;k<=i-1;k++)
             if(w[i]>=w[k]&&(m[k]+1>m[i]))
             m[i]=m[k]+1;
             if(m[i]>b)
             b=m[i];
     }
     cout<<b<<endl;
     return 0;
}