經(jīng)典的最長不下降子序列問題，O(n^2)【還存在基于二分查找的O(nlogn)算法】
方程：if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)
可能是今天狀態(tài)不好，一直在糾纏細(xì)節(jié).需要注意的是，子序列長度的最大值不一定在f[n]中.
1
#include<iostream>
2using namespace std;
3int a[5001], b[5001];
4
int max(int x, int y) 
{return (x > y) ? x : y;}
5int main()
6{
7
int i, j, n, ans;
8 cin >> n;
9
for (i = 1; i <= n; i++) {cin >> a[i]; b[i] = 1;}
10 for (i = 2; i <= n; i++)
11 {
12 for (j = 1; j < i; j++)
13 if (a[j] <= a[i] && b[j]+1 > b[i])
14 b[i] = b[j]+1;
15
}
16 for (i = 1; i <= n; i++)
17 if (ans < b[i]) ans = b[i];
18 cout << ans << endl;
19
}
20
馬上要走了，高中還是麻煩很多，進(jìn)度讓人糾結(jié).