每日OJ_牛客_最长递增子序列（dp/贪心模板）

目录

牛客_最长递增子序列（dp/贪心模板）

解析代码

牛客_最长递增子序列（dp/贪心模板）

最长公共子序列__牛客网

解析代码

在一个序列中找最长递增子序列，动态规划的典型应用，下面是两个模版

CISdp模板：

#include <iostream>
#include <vector>
using namespace std;

int LIS(vector<int>& arr)
{	// Longest increasing subsequence
	int n = arr.size(), res = 1;
	vector<int> dp(n, 1);
	for (int i = 1; i < n; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (arr[i] > arr[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
        res = max(res, dp[i]);
	}
	return res;
}

int main()
{
	int n = 0;
	while (cin >> n)
	{
        vector<int> arr(n);
        for(int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }
		cout << LIS(arr) << endl;
	}
	return 0;
}

LIS贪心模板：

#include <iostream>
#include <vector>
using namespace std;

int LIS(vector<int>& arr)
{
    int n = arr.size();
	vector<int> nums;
    nums.push_back(arr[0]);
	for (int i = 1; i < n; ++i)
	{
        if(arr[i] > nums.back())
        {
            nums.push_back(arr[i]);
        }
        else
        {
            auto it = lower_bound(nums.begin(), nums.end(), arr[i]);
            if(it != nums.end())
                *it = arr[i];           
        }
	}
	return nums.size();
}

int main()
{
	int n = 0;
	while (cin >> n)
	{
        vector<int> arr(n);
        for(int i = 0; i < n; ++i)
        {
            cin >> arr[i];
        }
		cout << LIS(arr) << endl;
	}
	return 0;
}