程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Longest Ordered Subsequence（最長單調遞增子序列）poj2533+動態規劃

Longest Ordered Subsequence（最長單調遞增子序列）poj2533+動態規劃

編輯：C++入門知識

Longest Ordered Subsequence（最長單調遞增子序列）poj2533+動態規劃

Longest Ordered Subsequence Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 40309 Accepted: 17743

Description

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence (a₁, a₂, ..., a_N) be any sequence (a_i₁, a_i₂, ..., a_{i_K}), where 1 <= i₁ < i₂ < ... < i_K <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

Source

Northeastern Europe 2002, Far-Eastern Subregion

題意：來自於 http://www.cnblogs.com/liyukuneed/archive/2013/05/26/3090402.html

本篇博客要繼續解決一個升級的問題——最長遞增子序列

問題定義：

給定一個長度為N的數組，找出一個最長的單調自增子序列（不一定連續，但是順序不能亂）。例如：給定一個長度為6的數組A{5， 6， 7， 1， 2， 8}，則其最長的單調遞增子序列為{5，6，7，8}，長度為4.

解法一：最長公共子序列法：

仔細思考上面的問題，其實可以把上面的問題轉化為求最長公共子序列的問題。原數組為A{5， 6， 7， 1， 2， 8}，下一步，我們對這個數組進行排序，排序後的數組為A‘{1， 2， 5， 6， 7， 8}。我們有了這樣的兩個數組後，如果想求數組A的最長遞增子序列，其實就是求數組A與它的排序數組A‘的最長公共子序列。我來思考下原問題的幾個要素：最長、遞增、子序列（即順序不變）。

遞增：A‘數組為排序數組，本身就是遞增的，保證了兩序列的最長公共子序列的遞增特性。

子序列：由於A數組就是原數組，其任意的子序列都是順序不變的，這樣就保證了兩序列的最長公共子序列的順序不變。

最長：顯而易見。

解法二：動態規劃法（O(N^2)）

既然是動態規劃法，那麼最重要的自然就是尋找子問題，對於這個問題，我們找到他的子問題：

對於長度為N的數組A[N] = {a0, a1, a2, ..., an-1}，假設假設我們想求以aj結尾的最大遞增子序列長度，設為L[j]，那麼L[j] = max(L[i]) + 1, where i < j && a[i] < a[j], 也就是i的范圍是0到j - 1。這樣，想求aj結尾的最大遞增子序列的長度，我們就需要遍歷j之前的所有位置i（0到j-1），找出a[i] < a[j]，計算這些i中，能產生最大L[i]的i，之後就可以求出L[j]。之後我對每一個A[N]中的元素都計算以他們各自結尾的最大遞增子序列的長度，這些長度的最大值，就是我們要求的問題——數組A的最大遞增子序列。

時間復雜度：由於每一次都要與之前的所有i做比較，這樣時間復雜度為O(N^2)。

解法三：動態規劃法（O(NlogN)）

上面的解法時間復雜度仍然為O(N^2)，與解法一沒有明顯的差別。仔細分析一下原因，之所以慢，是因為對於每一個新的位置j都需要遍歷j之前的所以位置，找出之前位置最長遞增子序列長度。那麼我們是不是可以有一中方法能不用遍歷之前所有的位置，而可以更快的確定i的位置呢？

這就需要申請一個長度為N的空間，B[N]，用變量len記錄現在的最長遞增子序列的長度。

B數組內任意元素B[i]，記錄的是最長遞增子序列長度為i的序列的末尾元素的值，也就是這個最長遞增子序列的最大元素的大小值。

首先，把d[1]有序地放到B裡，令B[1] = 2，就是說當只有1一個數字2的時候，長度為1的LIS的最小末尾是2。這時Len=1

然後，把d[2]有序地放到B裡，令B[1] = 1，就是說長度為1的LIS的最小末尾是1，d[1]=2已經沒用了，很容易理解吧。這時Len=1

接著，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是說長度為2的LIS的最小末尾是5，很容易理解吧。這時候B[1..2] = 1, 5，Len＝2

再來，d[4] = 3，它正好加在1,5之間，放在1的位置顯然不合適，因為1小於3，長度為1的LIS最小末尾應該是1，這樣很容易推知，長度為2的LIS最小末尾是3，於是可以把5淘汰掉，這時候B[1..2] = 1, 3，Len = 2

繼續，d[5] = 6，它在3後面，因為B[2] = 3, 而6在3後面，於是很容易可以推知B[3] = 6, 這時B[1..3] = 1, 3, 6，還是很容易理解吧？ Len = 3 了噢。

第6個, d[6] = 4，你看它在3和6之間，於是我們就可以把6替換掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len繼續等於3

第7個, d[7] = 8，它很大，比4大，嗯。於是B[4] = 8。Len變成4了

第8個, d[8] = 9，得到B[5] = 9，嗯。Len繼續增大，到5了。

最後一個, d[9] = 7，它在B[3] = 4和B[4] = 8之間，所以我們知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。

於是我們知道了LIS的長度為5。

注意，這個1,3,4,7,9不是LIS，它只是存儲的對應長度LIS的最小末尾。有了這個末尾，我們就可以一個一個地插入數據。雖然最後一個d[9] = 7更新進去對於這組數據沒有什麼意義，但是如果後面再出現兩個數字 8 和 9，那麼就可以把8更新到d[5], 9更新到d[6]，得出LIS的長度為6。

然後應該發現一件事情了：在B中插入數據是有序的，而且是進行替換而不需要挪動——也就是說，我們可以使用二分查找，將每一個數字的插入時間優化到O(logN)~~~~~於是算法的時間復雜度就降低到了O(NlogN)～！

根據上面的分析，下面是後兩種方法的C++代碼實現：

#include
#include
using namespace std;
int num[1005];
int main()
{
    int n;
    while(scanf(%d,&n)==1)
    {
        int tmp,mmax;
        scanf(%d,&tmp);
        mmax=tmp;
        int arr[1005];//用來存遞增序列，沒有實際意義
        arr[0]=tmp;
        int cnt=0;
        for(int i=1;itmp)
            {
                int left=0;
                int right=cnt;
                while(left<=right)//注意要到等號
                {
                    int mid=(left+right)/2;
                    if(arr[mid]tmp) right=mid-1;
                    if(arr[mid]==tmp) {left=mid; break;}
                }
                arr[left]=tmp;
            }
        }
        /**
        for(int i=0;i<=cnt;i++)
        {
            printf(%d ,arr[i]);
        }
        printf(
);
        */
        printf(%d
,cnt+1);
    }
    return 0;
}
/**
7
1 7 3 5 9 4 8
10
2 1 3 4 6 100 101 7 8 9
*/