最长递增子序列（LCS）

python：

提供两种解法。

第一种是正常的动态规则：

LIS是一个数组，里面维护的是每个位置最长上升子序列的值。在遍历数组的过程中，对应位置的LIS[i]都会得到更新，时间复杂度为O(n^2)。

def lengthOfLIS(nums):
    if not nums: return 0
    LIS = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and  LIS[i] < LIS[j] + 1:
                    LIS[i] = LIS[j] + 1
    return max(LIS)

print(lengthOfLIS(list(map(int, input().split()))))

也可以使用bisect模块，可以调试一下，观察每一步的变化：

import bisect

def lengthOfLIS(nums):
    q=[]
    for v in nums:
        pos=bisect.bisect_left(q,v)
        if pos==len(q):
            q.append(v)
        else:
            q[pos]=v
    return len(q)

print(lengthOfLIS(map(int,input().split())))

贪心 + 二分 做法

#include <iostream>

using namespace std;

const int N = 1e5+ 7;

int a[N], tail[N];

int main() {
    int i = 1;
    while (cin >> a[i]) {
        i++;
    }
    int n = i - 1;

    int len = 0;
    for (int i = 1; i <= n; i ++) {
        int x = a[i];

        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1>> 1;
            if (tail[mid] < x) l = mid;
            else r = mid - 1;
        }

        tail[l + 1] = x;
        len = max(len, l + 1);
    }

    cout << len << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100007;
const int INF = 0X7F7F7F7F;

int main()
{     int n=0, a[MAXN], LIS[MAXN];     while(cin>>a[n++]);     /*     for(int i=0;i<=n;i++)         LIS[i] = INF;     for(int i=0;i<n;i++)         *lower_bound(LIS,LIS+n,a[i]) = a[i];     cout<<(lower_bound(LIS,LIS+n,INF)-LIS)<<endl;     */     int len = 0;     for(int i=0;i<n;i++){         LIS[i] = 1;         for(int j=0;j<i;j++){             if(a[j]<a[i] && LIS[i]<LIS[j]+1)                 LIS[i] = LIS[j]+1;         }         len = max(len, LIS[i]);     }     cout<<len<<endl;     return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define INF 0X3F3F3F3F
const int MAX_N = 1E5 + 5;
int dp[MAX_N];
int a[MAX_N];
int n = 0;
void solve() {
    for (int i=0; i<=n; i++) {
        dp[i] = INF;
    }
    for (int i=0; i<n; i++) {
        *lower_bound(dp, dp+n, a[i]) = a[i];
    }
    printf("%d", lower_bound(dp, dp+n, INF) - dp);
}

int main() {
    while (scanf("%d", &a[n]) != EOF) {
        n++;
    }
    solve();
}

	

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Dynamic Programming
 *
 * State:
 *   dp[i]: 表示以a[i]为结尾的最长递增子序列的长度
 *
 * Initial State:
 *   dp[i] = 1    i属于[0, len(a))
 *
 * State Transition:
 *   i属于[0, len(a))
 *   if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1)  j属于[0, i)
 *
 * @author wylu
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            ArrayList<Integer> a = new ArrayList<>();
            while (scanner.hasNext()) {
                a.add(scanner.nextInt());
            }
            int[] dp = new int[a.size()];
            int res = 0;
            for (int i = 0; i < a.size(); i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (a.get(j) > a.get(i)) continue;
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
            System.out.println(res);
        }
    }
}

	

#include<stdio.h>

int main()
{
    int ai = 0, aj = 0;
    int cnt = 1;
    
    scanf("%d",&ai);
    while(scanf("%d",&aj) != EOF)
    {
        if(aj > ai)
        {
            cnt++;
        }
        else
        {
            ai = aj;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

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

int lengthOfLIS(const std::vector<int>& vec)
{
    std::vector<int> dp(vec.size(), 1);
    if(vec.size()<=1)
    {
        return vec.size();
    }
    int Max=dp[0];
    for(int i=1;i<dp.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            if(vec[i]>vec[j])
            {
                dp[i]=std::max(dp[j]+1, dp[i]);
            }
        }
        if(Max<dp[i])
        {
            Max=dp[i];
        }
    }
    return Max;
}

int main() 
{
    
    int x;
    int num=0;
    std::vector<int> arr;
    while (std::cin>>x) // 注意 while 处理多个 case
    { 
        arr.push_back(x);
    }
    std::cout<<lengthOfLIS(arr)<<std::endl;
}
// 64 位输出请用 printf("%lld")

package main

import (
    "fmt"
)

func main() {
    arr:=[]int{}
    var x int
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        arr=append(arr,x)
    }
    dp:=make([]int,len(arr))
    max:=0
    for i,x:=range arr{
        dp[i]=1
        for j:=0;j<i;j++{
            if arr[j]<x&&dp[j]+1>dp[i]{
                dp[i]=dp[j]+1
            }
        }
        if dp[i]>max{
            max=dp[i]
        }
    }
    fmt.Print(max)
}

const str = readline();
const list = str.split(' ').map(i=>parseInt(i))
let max = 0
// 1.长度为1直接就是1
if(list.length===1){
    max = 1
}else{
// 2. 否则需要处理
    for(let i=0,l=list.length;i<l;i++){
    let tempList = [] // 存储不连续的递增序列
    let index = 1 // 标记从1开始
    for(let j=i;j<l;j++){
        if(tempList.length){
            // 从1开始比较
            if(tempList[index] < list[j]){
                tempList.push(list[j])
                index++
            }
        }else{
            // 发现2个递增的直接存储 下次则从index为1开始比较
            if(list[i] < list[j]){
            tempList.push(list[i])
            tempList.push(list[j])
          }
        }
    }
    if(tempList.length >= max ){
        max = tempList.length
    }
    index = 1
 }
}
print(max)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> nums;

int main() {
    int x;
    while(cin >> x) {
        int t = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
        if(t < nums.size()) nums[t] = x;
        else nums.push_back(x);
    }
    cout << nums.size() << endl;
    return 0;
}

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

int main()
{
    vector<int> v;
    int temp;
    while(cin>>temp)
    {
        v.push_back(temp);
    }
    int ans=0;
    vector<int> dp(v.size(),1);
    for(int i=0;i<v.size();i++)
    {
        for(int j=v.size()-1;j>=i;j--)
        {
            if(v[j]>v[i]) dp[j]=max(dp[j],dp[i]+1);
            ans=max(ans,dp[j]);
        }
    }
    cout<<ans<<endl;
      
    system("pause");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int get_ans(vector<int>vec){
    if(!vec.size()) return 0;
    vector<int>ans;
    ans.push_back(vec[0]);
    for(int i=1; i<vec.size(); i++){
        int pos = upper_bound(ans.begin(), ans.end(), vec[i]) - ans.begin();
        if(pos==ans.size()) ans.push_back(vec[i]);
        else ans[pos]=vec[i];
    }
    return ans.size();
}

int main(){
    int x;
    vector<int>vec;
    while(~scanf("%d", &x)){
        vec.push_back(x);
    }
    printf("%d\n", get_ans(vec));
    return 0;
}

#include<iostream>
(720)#include<vector>
using namespace std;
//一遍dp即可,比如用例1 -1 2 -2 3 -3 4，一遍dp之后为1121314，去dp数组中最大值4为最长递增子序列。
int main()
{
    vector<int> queue;
    int n;
    while(cin>>n){
        queue.push_back(n);
    }
    vector<int> dp(queue.size(),1);
    for(int i=0;i<queue.size();i++){
        for(int j=i-1;j>=0;j--){
            if((queue[i]>queue[j])&&(dp[i]<dp[j]+1)){
                dp[i] = dp[j] + 1;
            }
        }
    }
    int max=0;
    for(int i=0;i<queue.size();i++){
        if(dp[i]>max)max=dp[i];
        //cout<<dp[i];
    }
    cout<<max<<endl;
    return 0;
}

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    String[] strs=sc.nextLine().split(" ");
    int[] nums=new int[strs.length];
    for(int i=0;i<strs.length;i++){
        nums[i]=Integer.valueOf(strs[i]);
    }
    int ret=fun(nums);
    System.out.println(ret);
    }
    private static int fun(int[] nums){
        if(nums.length==0||nums==null) return 0;
        if(nums.length==1) return 1;
        int[] dp=new int[nums.length];
        int max=0;
        for(int i=0;i<nums.length;i++ ){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(dp[i],max);
        }
        return max;
    }
}