#include <iostream>

#include <limits.h>

#include <vector>

#include <algorithm>

using namespace std;

//获取最长递增子序列的递增数组

vector<int> getdp1(vector<int> arr) {

    vector<int> dp(arr.size());

    for (int i = 0; i < int(arr.size()); i ++) {

        dp[i] = 1;

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

            if (arr[i] > arr[j])

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

        }

    }

    return dp;

}

vector<int> getdp2(vector<int> arr) {

    int right = 0;

    int arr_len = int(arr.size());

    int ends[arr_len];

    int dp[arr_len];

    ends[0] = arr[0];

    dp[0] = 1;

    for (int i = 1; i < arr_len; i ++) {

        //二分查找ends

        int l = 0;

        int r = right;

        while (l <= r) {

            int mid = (l + r) >> 1;

            if (arr[i] > ends[mid])

                l = mid + 1;

            else

                r = mid - 1;

        }

    }

}

// 从dp数组中逆序还原出决策路径

vector<int> generateLIS(vector<int> dp, vector<int> arr) {

    vector<int>::iterator  maxPosition = max_element(dp.begin(), dp.end()); //algorithm中求vector最大值的函数

    int maxIndex = maxPosition - dp.begin();

    int maxNum = *maxPosition;

    vector<int> res;

    res.push_back(arr[maxIndex]);

    int tmpNum = maxNum;

    for (int i = maxIndex - 1; i >= 0; i --) {

        if (dp[i] == tmpNum - 1) {

            res.push_back(arr[i]);

            tmpNum -= 1;

        } else continue;

    }

    reverse(res.begin(), res.end());

    return res;

}

int main()

{

    vector<int> test = {2, 1, 5, 3, 6, 4, 8, 9, 7};

    vector<int> dp =  getdp1(test);

    vector<int> lis = generateLIS(dp, test);

//    cout<<"LIS"<<lis.size()<<endl;

    for (auto c: lis)

        cout<<c<<endl;

    return 0;

}