動态規劃--最長上升子序列

總時間限制:2000ms

記憶體限制:65536kB

描述

一個數的序列 bi，當 b1 < b2 < ... < bS的時候，我們稱這個序列是上升的。對于給定的一個序列( a1, a2, ..., aN)，我們可以得到一些上升的子序列( ai1, ai2, ..., aiK)，這裡1 <= i1 < i2 < ... < iK <= N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1, 3, 5, 8).

你的任務，就是對于給定的序列，求出最長上升子序列的長度。

輸入

輸入的第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的N個整數，這些整數的取值範圍都在0到10000。

輸出

最長上升子序列的長度。

樣例輸入

7 1 7 3 5 9 4 8

樣例輸出

4

題目大概：

給定一個序列，從中找出最長的上升子序列。

思路：

這是動态規劃題。 1.。。首先是子問題，如要求n個數的最長上升子序列問題，第i個數當最後一個數的最長上升子序列問題。 2.。。狀态，b[n]代表以第n個數結尾的最長上升子序列。a[n]表示第n個數的數值。 3.。。狀态轉移方程，                        a[i]<a[n]時    b[n]=max(b[i](1<i<=n)); 簡單的說就是先求n左邊的最長的子序列（a[i]<a[n]）加1.作為第n個數的最長子序列。 然後用循環求出所有的數的最長的一個。

感想：

這個題說起來多，其實做起來代碼也不多。

代碼：

#include <iostream>

using namespace std ;

int main ()

{ int n ,ma = 0 ,sum = 0 ;

int a [ 1001 ]= { 0 } ,b [ 1001 ]= { 0 } ;

b [ 1 ]= 1 ;

cin >>n ;

for ( int i = 1 ;i <=n ;i ++)

{cin >>a [i ]; }

for ( int i = 2 ;i <=n ;i ++)

{

ma = 0 ;

for ( int t = 1 ;t <i ;t ++)

{ if (a [i ]>a [t ]) {

if (b [t ]>ma ) {ma =b [t ]; }

}

     }

     b [i ]=ma +1 ;

}

for ( int i = 1 ;i <=n ;i ++)

{ if (sum <b [i ])sum =b [i ];

}

cout <<sum ;

    return 0 ;

}