普通情况：
- #include <stdio.h>
- #include <algorithm>
- #include <string.h>
- using namespace std;
- int a[1005],dp[1005],n;
- int LIS()
- {
- int i,j,ans,m;
- dp[1] = 1;
- ans = 1;
- for (i = 2;i<=n;i++)
- {
- m = 0;
- for (j = 1;j<i;j++)
- {
- if (dp[j]>m && a[j]<a[i])
- m = dp[j];
- }
- dp[i] = m+1;
- if (dp[i]>ans)
- ans = dp[i];
- }
- return ans;
- }
二分优化
- #include <stdio.h>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- int a[40005],dp[40005],n;
- int bin( int size, int k)
- {
- int l = 1,r = size;
- while (l<=r)
- {
- int mid = (l+r)/2;
- if (k>dp[mid])
- l = mid+1;
- else
- r = mid-1;
- }
- return l;
- }
- int LIS()
- {
- int i,j,ans=1;
- dp[1] = a[1];
- for (i = 2; i<=n; i++)
- {
- if (a[i]<=dp[1])
- j = 1;
- else if (a[i]>dp[ans])
- j = ++ans;
- else
- j = bin(ans,a[i]);
- dp[j] = a[i];
- }
- return ans;
- }
