最长上升子序列

有一个长为n的数列a0,a1,---,an-1.求出这个序列中最长的上升子序列的长度,限制条件是1<=n<=1000,0<=ai<=1000000;

int dp[1000];

int number[1000];

第一种dp是将dp[i]看做到i为止的最长子序列的个数,递推关系是从前i-1个dp元素中选出number[x]小于a[i],即可将a[i]加入最长子序列中所以dp[x]+=1,dp[i]的值就是遍历a[0]到a[i]得到最大dp[x]

递推公式dp[i]=max(1,dp[j]+1),j<i

int i = 0;

int res = 0;

cin >> i;

for (int j = 0; j < i; j++)

{

dp[j] = 1;

cin >> number[j];

for (int k = 0; k < j; k++)

{

if (number[j] > number[k])

{

res = max(dp[j], dp[k]+1);

}

dp[j] = max(res, dp[j]);

 }

 }

cout << "最大为"<<dp[i-1];

cin >> i;

第二种方把dp数组代表最长子序列本身，dp[i]为到i为止的最长子序列中最大值(最小的最大值,有比他小的即更新,但比前面i-1个要小)，这样能通过下标来判断个数

int res = 0;

int middleMax( int a)

{

if (dp[res] < a) {

res++;

return res;

}

int first = 0;

int last = res;

while (last!=first)

{

int middle = (first + last) / 2;

if (dp[middle] < a)

{

first = middle;

}

else if (dp[middle] == a)

{

return middle;

}

else

{

last = middle;

}

}

for (int q = 0; q < i; q++)

{

dp[q] = maxNumber;

cin >> number[q];

dp[middleMax( number[q])] = number[q];

}

int s = 0;

for (int k = 0; k < i; k++)

{

if (dp[k] < maxNumber)

s++;

else

break;

}

cout << s;

个人目前理解DP是记录各个子问题的解,通过各个子问题的解求出问题的解,如子序列的最长个数是序列的最长个数的子问题，整个序列的最长个数通过遍历所有的子问题得出最大值。DP[i]表示什么也很重要,第二种DP[i]跟第一种表示不同，但是时间复杂度更少，是O(n*logn)再就是递归方程式,写出来才能做下去，个人愚见，权当学习记录