！壞人必需做好事！

執行結果：

41 67 34 0 69 24 78 58 62 64
5 45 81 27 61 91 95 42 27 36
91 4 2 53 92 82 21 16 18 95
47 26 71 38 69 12 67 99 35 94
3 11 22 33 73 64 41 11 53 68
47 44 62 57 37 59 23 41 29 78
16 35 90 42 88 6 40 42 64 48
46 5 90 29 70 50 6 1 93 48
29 23 84 54 56 40 66 76 31 8
44 39 26 23 37 38 18 82 29 41
length: 16
95 92 82 71 69 67 64 62 59 50 48 44 39 26 23 18

程式碼：

// Longest Increasing Subsequence
// 參考 PingLunLiao 來自 http://www.csie.nfu.edu.tw/phpBB3/viewtopic.php?p=64580

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    using namespace std;
    vector<int> num;
    int input;
    int i;
    // random generate number
    for (i = 0;i<100;i++)
        num.push_back(rand()%100);
    // print data
    for (vector<int>::iterator it = num.begin();
        it != num.end();it++)
    {
        if (i%10 == 0) cout << endl;
        cout << *it << " ";
        i++;
    }
    cout << endl;
    vector<int> best;
    best.resize(num.size());

    best[0] = 1;
    int maxLen = 1;

    // Dynamic Programming:
    // if( num[i] > num[k] )
    // best[i] = max(best[0] ... best[k])
    for( int i = 1; i < num.size(); i++ )
    {
        short tempBest = 0;
        //find an (number) that smaller than (num[i]) and have (sequence length) that biggest!
        for( int k = i - 1; k >= 0; k-- )
        {
            if( num[i] < num[k] )
            {
                if( tempBest < best[k] )
                {
                    tempBest = best[k];
                }
            }
        }
        best[i] = tempBest + 1;
        if( best[i] > maxLen ) maxLen = best[i];
    }
    // get Longest Increasing Subsequence's length
    int minindex = std::max_element(best.begin(), best.end()) - best.begin() ;
    int minmum = num[minindex];
    int minvalue = best[minindex];
    cout << "length: " << minvalue << endl;
   vector<int> answer;
    // inverse print answer
    for (int i = num.size()-1;i >= 0;i--)
    {
        if (best[i] == minvalue)
        {
            if (minmum <= num[i])
            {
                --minvalue;
                minmum = num[i];
                answer.push_back(num[i]);;
            }
        }
    }
    reverse(answer.begin(), answer.end());
    for (int i=0;i < answer.size();i++)
        cout << answer[i] << " ";

    return 0;
}