首页 > 试题广场 >

最长上升子序列

[编程题]最长上升子序列

热度指数：5611 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。

输入描述:

输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。

紧接着第二行包含n个正整数m（1≤n≤10000），代表队伍中每位队员的身高。

输出描述:

对应每一组数据，输出最长递增子序列的长度。

示例1

输入

7
1 7 3 5 9 4 8
6
1 3 5 2 4 6

输出

4
4

算法知识视频讲解

北门小庆庆

// write your code here cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector<int> height(n, 0);
        for(int i = 0; i < n; i ++){
            cin >> height[i];
        }
        
        vector<int> f(n, 1);
        int result = 1;
        for(int i = 1; i < n; i ++){
            for(int j = 0; j < i; j ++){
                if(height[i] > height[j]){
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            result = max(result, f[i]);
        }
        
        cout << result << endl;
    }
}

发表于 2016-09-05 15:52:53 回复(0)

Python

华科平凡

烂大街的题目。python解法，时间复杂度nlogN

import bisect

while True:
    try:
        a, b = input(), map(int, input().split())
        q = []
        for i in b:
            pos = bisect.bisect_left(q, i)
            if pos == len(q):
                q.append(i)
            else:
                q[pos] = i
        print(len(q))
    except:
        break

发表于 2017-10-11 15:15:13 回复(1)

晓宇大美女~

// write your code here
import java.util.Scanner;

public class Main {
	
	
	public static int findLongest2(int[] A, int n){
		int[] dp = new int[n];
		dp[0] = 1;
		
		int[] ends = new int[n];
		
		ends[0] = A[0];
		//右哨兵
		int right = 1;
		
		int maxLength = dp[0];
		for(int i = 1;i<n;i++){
			//二分查找第一个比自己大的数，替代之，如果没找到，写在后边
			int start = 0;
			int end = right-1;
			int resultPos = right;
			while(start <= end ){
				int mid = start + (end - start)/2;   //重要
				if(ends[mid]>=A[i]){
					resultPos = mid;
					end = mid - 1;
				}else
					start = mid + 1;
			}
			ends[resultPos] = A[i];
			if(resultPos == right)
				right++;
			dp[i] = resultPos + 1;
			maxLength = Math.max(maxLength, dp[i]);
		}
		return maxLength;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int[] data = new int[n];
			for(int i = 0;i<n;i++){
				data[i] = sc.nextInt();
			}
			System.out.println(findLongest2(data, n));
		}
	}
}

发表于 2016-10-10 11:25:49 回复(0)

后劲好大

import java.util.Scanner;

/**
 * Created by Olive on 2017/9/7.
 * ***上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，
 * 请你帮忙找出身高依次递增的子序列。 例如队伍的身高数据是（1、7、3、5、9、4、8），
 * 其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。
 */
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] height = new int[n];
            for(int i = 0; i < n; i++){
                height[i] = in.nextInt();
            }
            System.out.println(longest(height, n));
        }
    }

    public static int longest(int[] height, int n){
        if(height == null || n <= 0 || height.length != n)
            return 0;
        // dp[i]代表以i为结尾的最长递增子序列的长度
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(height[i] > height[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            if(max < dp[i])
                max = dp[i];
        }

        return max;
    }
}

发表于 2017-09-07 11:20:47 回复(0)

wcz2023

#include <iostream>
using namespace std;
int main(){
    int N;
    while(cin >> N){
        int  a[10002], dp[10002] = {0}, m=0;
	for (int i = 1; i <= N; i++) cin >> a[i];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j < i; j++)
			if (a[j] < a[i])
				dp[i] = max(dp[i], dp[j] + 1), m = dp[i] > m ? dp[i] : m;
	cout << m + 1 << endl;
    }
    return 0;
}

发表于 2016-09-01 14:58:59 回复(0)

Python

TimeMac

Python自实现时间复杂度O（nlogn）

创建一个数组subSeries，数组保存着0~i 的当前子序列最长的上升序列最后一个数的最小数

（每个位置放着比下标大一的上升子序列长度中的最后一个（也是相同长度的最小值））

可以输出观察

如果该数组有记录的话,如果你比该数组的最后一个数大的话，把该数添加到辅助数组中，最大递增子序列加一

否则在里面查找到比你大的最小数的前面替换掉，在数组的下标其实就是以该数结尾的最长子序列长度

try:
    while True:
        num,digitsList = int(input()),list(map(int,input().split()))
        subSeries = []
        maxLen = 0
        subSeries.append(digitsList[0])  #辅助数组
        for i in range(1,num):
            if digitsList[i] > subSeries[maxLen]:
                maxLen += 1
                subSeries.append(digitsList[i])
            else:
                left,right = 0,maxLen
                while left <= right:    #在已有的subSeries数组范围内二分查找到比该数大的最小数替换掉
                    mid = (left+right)//2
                    if digitsList[i] > subSeries[mid]:
                        left = mid+1
                    else:
                        right = mid-1
                subSeries[left] = digitsList[i]
    #        print(" ".join(map("{:>2}".format, subSeries)))  #每次打印出来观察
        print(maxLen+1)
except Exception:
    pass

编辑于 2018-09-23 22:44:20 回复(0)

泽恩泽恩

import java.util.Scanner;
public class Main{
 	   public static void main(String[] args){
	        Scanner cin=new Scanner(System.in);
	        while(cin.hasNext()){
	            int number=cin.nextInt();
				int result=1;//结果
	            int[] arr=new int[number];//数据初始化
	            for(int i=0;i<number;i++){
	                arr[i]=cin.nextInt();
	            }
	            int[] dp=new int[number];
	            dp[0]=1;
	            for(int i=0;i<number;i++){
	                dp[i]=1;
	                for(int j=0;j<i;j++){
	                    if(arr[j]<arr[i]&&dp[j]>=dp[i]){
                            dp[i]=dp[j]+1;
                            result=dp[i]>result?dp[i]:result;
                        }
	                }
	            }
	            System.out.println(result);
	            
	        }
	    }
	}

发表于 2017-09-10 15:52:31 回复(0)

324134134143428

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#define N 1001

using namespace std;

int main()

{

int n;

while(cin>>n){

int a[N];//这个是干什么的呢？？？没错，他就是存

int maxLen[N];//这个有什么用呢，，，，，

//首先这个运用，递推，动规的思想，求最后一个的最长子序列，这个数组存的是到达每个数的

//最长子序列，ps:除了第一个数

for(int i = 1;i<=n;i++)

{

cin>>a[i];

maxLen[i] = 1;//默认每个初始化为1，其实我感觉0也可以，不过有的地方需要改下，稍微麻烦了点

//喜欢的可以自己试试，ps:用0的话就是你自己写出来的了，而不是借鉴别人的了

}

for(int i = 2;i<=n;i++)

{

for(int j = 1;j<i;j++)

if(a[i]>a[j])

maxLen[i] = max(maxLen[i],maxLen[j]+1);

//这里max函数用的不是很熟练，

}

cout<<*max_element(maxLen+1,maxLen+n+1)<<endl;

}

//ps:

/*我感觉还是解释一下比较好，

还有本次本来准备用vector的，不准备用数组了，但是由于不熟练总是出错，

所以又换成a[N]了

以上是在看了郭炜老师的课件之后写出来的*/

发表于 2017-07-25 13:07:02 回复(0)

C/C++

Cavs

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int n;
	while (cin >> n && n > 0)
	{
		vector<int> height(n), dp(n, 1);
		int maxLen = 1;
		for (int i = 0; i < n; ++i)
		{
			cin >> height[i];
			for (int j = i - 1; j >= 0; --j)
				if (height[j] < height[i]) dp[i] = max(dp[i], dp[j] + 1);
			maxLen = max(maxLen, dp[i]);
		}
		cout << maxLen << endl;
	}

	return 0;
}

发表于 2017-07-11 21:20:35 回复(0)

Java

孙强Jimmy

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			int[] m = new int[n];
			for (int i = 0; i < n; i++) {
				m[i] = sc.nextInt();
			}
			int[] dp = new int[n];
			dp[0] = 0;
			int max = 0;
			for (int i = 1; i < n; i++) {
				for (int j = 0; j < i; j++) {
					if (m[j] < m[i]) {
						dp[i] = Math.max(dp[j] + 1, dp[i]);
						if (max < dp[i]) {
							max = dp[i];
						}
					}
				}
			}
			System.out.println(max + 1);
		}
	}
}

编辑于 2017-03-22 21:54:17 回复(0)

C/C++

Ziscor

#include <cstring> 
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#define MAX 1000+5
using namespace std;

int n;
int dp[MAX];//dp[i]表示长度为i+1的最长上升子序列的末尾元素最小值
int m[MAX];
int LIS(int* m){
	int len=0;
	dp[len]=m[0];
	for(int i=1;i<n;++i){
		if(dp[len]<m[i]){
			dp[++len]=m[i];
		}
		else{
			*lower_bound(dp,dp+len,m[i])=m[i];//二分查找
		}
	}
	return len+1;
}
int main()
{
	while(scanf("%d",&n)!=EOF){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;++i)
			scanf("%d",&m[i]);
		if(m){
			printf("%d\n",LIS(m));
		}
	}
	return 0;
}

发表于 2016-11-29 23:22:04 回复(0)

OOACMer

  classAscentSequence { 

  public: 

      intfindLongest(vector<int> A, intn) { 

          // write code here 

          vector<int> B; 

          intmax = 0; 

          for(inti=0;i<n;i++){ 

              B.push_back(1); 

              for(intj=i-1;j>=0;j--) 

              { 

                  if(A[j]<A[i]) B[i] = B[j]>=B[i]?B[j]+1:B[i]; 

              } 

              max = max>B[i]?max:B[i]; 

          } 

          returnmax; 

      } 

  }; 

  之前做过的题：：程序借助辅助vector<int>
  B，B中元素记录A中对应元素当前最大升序值，B[i]初始化为1，遍历A中元素来更新B[i]的值，max记录最大升序长度。 

  有不了解的地方请回复！！！

发表于 2015-08-07 13:24:37 回复(0)

C/C++

phonkivon

// write your code here cpp
#include<iostream>
#include<vector>
using namespace std;
int getHeight2(vector<int> men, int n)
{ //法二: help数组加速   时间复杂度O(nlogn)
 int* help=new int[n];
 int left=0,right,mid,r=0;
 if(n==0) return 0;
 help[0]=men[0];
 for(int i=1;i<n;i++)
 {
  if(men[i]>help[r]){r++;help[r]=men[i];}
  else{
    left=0;
          right=r;
    while(left<=right)
    {
     mid=(left+right)/2;
     if(men[i]>help[mid])left=mid+1;
     else right=mid-1;
    }
    help[left]=men[i];
  }
 }
 delete[] help;
    return r+1;
}
 
int main()
{
 int n;
    while(cin>>n){
 int* b=new int[n];
 for(int i=0;i<n;i++)
  cin>>b[i];
    vector<int> a(b,b+n);
    cout<<getHeight2(a,a.size())<<endl;
 delete []b;
 }
 return 0;
}
思路：构造一个辅助数组help，help数组维持了一个递增序列，依次遍历原始数组，如果大于help数组的最后一个数（最大的数），将其加入help数组末尾，help数组长度增长，else 用二分法找到第一个比当前元素大的数，并用当前元素替换该数。这样遍历结束，help维持的递增序列长度就是所求的数。

发表于 2016-09-05 21:38:08 回复(3)

掉下个小石头

简单的动态规划，O(n**2)即可AC，当然不嫌麻烦也可以修改为O(n log n).

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

int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> data(n);
		vector<int> state(n);
		for (int i = 0; i<n; i++)
		{
			cin >> data[i];
			int maxlength = 0;
			for (int j = 0; j<i; j++)
			{
				if (data[j]<data[i])
				{
					if (state[j]>maxlength)
						maxlength = state[j];
				}
			}
			state[i] = maxlength + 1;
		}
		int result = 0;
		for (int i = 0; i<n; i++)
			result = result>state[i] ? result : state[i];
		cout << result << endl;
	}
}

发表于 2016-09-05 14:54:08 回复(0)

DuXinyu

这个是个动态规划的一个问题，我们这样来理解这个题，我们先假设只有俩个数字，那么我们只需要看第二个数字是不是比第一个数字大，如果打的话就是2，否则就是1，那么我们现在假设有三个数字，我们先看前俩个数字，和刚才一样的方法，然后我们看第三个数字是不是比第二个数字大，大的话我们就在第二个数字对应的那个长度上加1为第三个数字，所以我们可以借助一个辅助数组来存储对应数字的长度，然后我们遍历一遍就可以得到最长的数字

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

void mostlong(vector<int>& v)
{
	vector<int> arr(v.size(), 1);
	int sum = 1;
	for (size_t i = 1; i < v.size(); i++)
	{
		for (size_t j = 0; j < i; j++)
			if (v[i] > v[j])
				arr[i] = max(arr[i], arr[j] + 1);

		sum = max(sum, arr[i]);
	}
	cout << sum << endl;
}

int main()
{
	int num = 0;
	while (cin >> num)
	{
		vector<int> v(num, 0);
		for (int i = 0; i < num; i++)
			cin >> v[i];

		mostlong(v);
	}

	return 0;
}

发表于 2020-07-30 22:51:48 回复(0)

一个达布刘

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


int LIC(vector<int> &v,int n)
{
    vector<int> dp(n,1);
    int res=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[i]>v[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        res=max(res,dp[i]);
    }
    return res;
}

int main() {
    int n;
    int result;
    while (cin >> n)
    {
        vector<int> v(n);
        for(int i=0;i<n;i++)
        {
            cin>>v[i];
        }
        cout<<LIC(v,n)<<endl;
    }
    return 0;
}

发表于 2023-11-07 16:56:48 回复(0)

C/C++

寄了的潜伏者很想去夏威夷

必须是严格递增(>)，而不是非递减(>=)

#include <stdio.h>

int main(){
    int n, arr[10000],dp[10000];
    while(~scanf("%d",&n)){
        int maxLen=1,i,j;
        scanf("%d",&arr[0]);
        dp[0]=1;
        for(i=1;i<n;i++){
            scanf("%d",&arr[i]);
            int curMaxLen=1;
            for(j=i-1;j>=0;j--){
                if(arr[i]>arr[j] && dp[j]+1>curMaxLen){
                    curMaxLen=dp[j]+1;
                }
            }
            dp[i]=curMaxLen;
            if (curMaxLen>maxLen) maxLen=curMaxLen;
        }
        printf("%d\n",maxLen);
    }
    return 0;
}

发表于 2023-01-10 16:05:41 回复(0)

Java

two倩

import java.util.Scanner;

/**
* Created with IntelliJ IDEA.
* Description:
* User:是two倩呀！
* Data:2022-09-23
* Time:16:01
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
if (n == 0) {
System.out.println(0);
continue;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}

int[] dp = new int[n];
for (int i = 0; i < n; i++) {//每一个元素都可以自身构成一个子序列
dp[i] = 1;
}
int result = 1;//最起码存在自身元素构成的序列
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//dp[i]此时是以i为底的最大值但是不意味着dp[n-1]一定是最大的
result = Math.max(dp[i], result);
}
System.out.println(result);
}
}
}

发表于 2022-09-23 20:57:29 回复(0)

来学习的小张

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] res = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = sc.nextInt();
            //res数组里面的元素都初始化为1
            res[i] = 1;
        }
        
        for(int i = 1;i < arr.length;i++){
            for(int j = 0;j < i;j++){
                //遍历i之前的数，如果i位置的元素大，就动态规划进行比较
                if(arr[i] > arr[j]){
                    res[i] = Math.max(res[i],1 + res[j]);
                }
            }
        }
        
        //最后返回res里面存储的最长子序列的值
        int t = Integer.MIN_VALUE;
        for(int i = 0;i < res.length;i++){
            if(t < res[i]){
                t = res[i];
            }
        }
        System.out.println(t);
        }
    }
}

发表于 2022-06-03 11:56:11 回复(0)

大大的糖果果

二分查找调试半天，我是真的菜

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int ln = sc.nextInt();
            int size = 0;
            int[] nums = new int[ln];
            while(ln-->0){
                int n = sc.nextInt();
                if(size != 0 && nums[size-1] >= n){
                    nums[findeIndex(nums,size,n)] = n;
                }else if(size == 0){
                    nums[size++] = n;
                }else if(nums[size-1] < n){
                    nums[size++] = n;
                }
            }
            System.out.println(size);
        }
    }
    private static int findeIndex(int[] nums,int size,int n){
        int i = 0 , j = size - 1,mid = j >> 1;
        while(i < j){
            if(nums[j] < n){
                return j + 1;
            }
            if(nums[mid] < n){
                i++;
                mid = i + ((j - i) >> 1);
            }else if(nums[mid] > n){
                j--;
                mid = i + ((j - i) >> 1);
            }else{
                break;
            }
        }
        return nums[mid] < n ? mid + 1 : mid;
    }
}

编辑于 2022-05-20 03:10:32 回复(1)