# 題目: UVa 481 - What Goes Up

# 題目說明

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

---

INPUT:
輸入一連串的整數

---

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

# 解題方法

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

# 參考程式碼

#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