# 題目: UVa 481 - What Goes Up

# 題目說明

給一串整數序列，找出 最長的嚴格遞增子序列 ( strictly increasing subsequence )

INPUT:
輸入一連串的整數

OUTPUT:
輸出 最長的嚴格遞增子序列 的長度與其中的元素
(若有多組元素的長度一樣，以最後出現的為準)

將資料存取後，利用貪婪演算法找出嚴格遞增子序列的長度
紀錄每次選取的位置
vector V 儲存輸入的整數
vector S 儲存現在的嚴格遞增子序列
vector dp 儲存元素的位置

若使用動態規劃，時間複雜度會為 O(N^2) ，會超時
所以改用貪婪演算法，將時間複雜度降至 N * log(N)

	#include <iostream>
	#include <vector>

	using namespace std;

	int main()
	{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int a, L = 1;
	vector<int> V;
	vector<int> S;
	vector<int> dp;
	vector<int> ans;

	while (cin >> a) V.emplace_back(a);
	dp.assign(V.size() + 1, 0), dp[0] = L;
	S.emplace_back(V[0]);

	for (int i = 1; i < V.size(); ++i)
	{
	if (V[i] > S.back())
	{
	S.emplace_back(V[i]);
	dp[i] = ++L;
	}
	else
	{
	auto it = lower_bound(S.begin(), S.end(), V[i]);
	*it = V[i];
	dp[i] = (it - S.begin() + 1);
	}
	}

	for (int i = V.size() - 1; i >= 0; --i) if (dp[i] == L)
	{
	ans.emplace_back(V[i]);
	--L;
	}

	cout << ans.size() << "\n-\n";
	for (int i = ans.size() - 1; i >= 0; --i) cout << ans[i] << "\n";

	return 0;
	}

https://yuihuang.com/dp-lis/
http://web.ntnu.edu.tw/~algo/Subsequence.html