最长上升子序列(dp 贪心+二分) 俄罗斯套娃_最长上上生子序列贪心

铺垫： 

注意：子序列是不连续的哦！

方法一(dp)O(n^2)：

分析：

dp[i] 表示的是以a[i]结尾的最大严格单调递增子序列的长度 那么在1到i-1之间，if a[j] < a[i] 那么可以达到dp[i] = max(dp[i], dp[j] + 1)  最后的答案枚举一下1-n的dp,看看以谁为末尾的长度最长

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N = 1010;
int dp[N];
int a[N];
int n;
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = 1;// 因为 它自己也算一个  
        for (int j = 1; j < i; j ++ )
        {
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int  res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dp[i]);
    cout << res << endl;
    return 0;
}

方法二：(贪心+二分)O(nlogn):

分析:

就是让替换后的数组更加有潜力 也就是 后面有数更容易插进来,比如1, 2和1,4 谁更有潜力呢？很显然1, 2 更加有潜力，因为后面出现3的时候3可以插在1, 2后面 但是不可以插在1,4的后面

模拟过程:

 代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
int a[N], b[N];
int n, m, len;
 
int find(int x) {
	//找到第一个大于等于x的数
	int l = 0, r = len + 1;
	while(l + 1 < r) {
		int mid = l + r >> 1;
		if(b[mid] < x)l = mid;
		else r = mid;
	} 
	return l + 1;
}
 
signed main() {
	cin >> n;
	for(int i = 1; i <= n; ++ i)cin >> a[i];
	len = 1;
	b[1] = a[1];
	
	for(int i = 2; i <= n; ++ i ) {
		if(a[i] > b[len])b[++len] = a[i];
		else {
			int j = find(a[i]);
			b[j] = a[i];
		}
	}
	cout << len << endl;
	return 0;
}

俄罗斯套娃问题 

354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

分析：

这里的n最大是1e5,因此O(n^2)是不行的了，只能去用二分+贪心了(nlogn)

先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个h数组上计算最长上升子序列的长度就是答案,因为w数组已经是从小到大的了。这里的h为什么要按照降序排序呢？举个例子[1, 2] 和 [1, 3] 要是这样的话 咱们算的是[1, 2]可以插在[1, 3]的前面 这是不对的，因此我们当这个w一样的时候，咱们按照h降序比如[1, 3], [1, 2]这样就不会出现错误了

java代码：

import java.util.Arrays;
import java.util.Comparator;
 
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        //先按照第一个升序排序 再按照第二个 降序排序 然后在第二个里面求最长上升子序列
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                } else {
                    return o2[1] - o1[1];
                }
            }
        });
 
        int len = 0;
        int[] b = new int[envelopes.length + 1];
        b[0] = envelopes[0][1];
        int n = envelopes.length;
 
        for(int i = 1; i < n; ++ i ) {
            if(envelopes[i][1] > b[len]) {
                b[++len] = envelopes[i][1];
            } else {
                int x = envelopes[i][1];
                //二分查找第一个大于等于的数
 
                int l = -1, r = len;
                while(l + 1 < r) {
                    int mid = l + r >> 1;
                    if(b[mid] < x)l = mid;
                    else r = mid;
                }
                b[l + 1] = x;
            }
        }
        return len + 1;
    }
}