//问题：找最长递增子序列（可以不要求连续）
/*
方法：动态规划
dp[i]表示以nums[i]为结尾的最长递增子串的长度
dp[i] = max(dp[i], dp[j] + 1)
O(n^2) O(n)
*/
class Solution
{
public:
int lengthOfLIS(vector<int>& nums)
{
vector<int> dp(nums.size(), 1); //dp值初始化为1，dp[0] = 1,一个元素长度为1
int res = 0;
for (int i = 0; i < nums.size(); i++) //遍历数组，以num[i]结尾
{
for (int j = 0; j < i; j++) //遍历num[i]以前的数（i=0~n-1,j=0~i-1）
{
if (nums[j] < nums[i] )//当遇到递增对时，dp[j]+1,更新dp[i]
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]); //选择dp[i]中的最大值，因为不确定以哪个num[i]结尾的递增子序列最长
}
return res;
}
/*
掌握
* 方法：动态规划+二分查找
* 具体过程：dp存最长递增子序列
* 例：
input: [0, 8, 4, 12, 2]
dp: [0]
dp: [0, 8]
dp: [0, 4]
dp: [0, 4, 12]
dp: [0 , 2, 12] which is not the longest increasing subsequence, but length of dp array results in length of Longest Increasing Subsequence.
* O(nlogn) O(n)
*/
#include <algorithm>
class Solution
{
public:
int lengthOfLIS(vector<int>& a)
{
if(a.empty()) return 0;
vector<int> dp;
for (int ai : a)
{
//lower_bound返回第一个大于等于ai的位置,函数参数为（first,last） last指向区间末尾位置
//在dp[first,last)序列中寻找ai可以满足增序插入的位置，如果找不到，说明ai比区间所有值大，返回last
auto it = lower_bound(dp.begin(), dp.end(), ai); //查找第一个大于等于ai的位置(查找ai可以插入的位置)
if (it == dp.end()) //如果区间中不存在，则push到末尾
dp.push_back(ai);
else //如果存在，则替换对应位置的元素
*it = ai;
}
return dp.size();
}
};
