首页 > 试题广场 >

最长递增子序列A

[编程题]最长递增子序列A
  • 热度指数：3468 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.



输入描述:

第一行包含一个整数T，代表测试数据组数。

对于每组测试数据：
N-数组的长度

a1 a2 ... an （需要计算的数组）

保证：

1<=N<=3000,0<=ai<=MAX_INT.


输出描述:

对于每组数据，输出一个整数，代表最长递增子序列的长度。
示例1

输入

2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出

3
3
算法知识视频讲解
添加回答
世界之末头像 世界之末 
#include<iostream>
#include"vector"
using namespace std;

int main()
{
	vector<int>result;
	vector<int>result1;
	vector<int>num;
	int T;
	cin >> T;
	while (T--)
	{
		int a;
		cin >> a;
		int n = a;
		while (a--)
		{
			int b;
			cin >> b;
			num.push_back(b);
			result.push_back(1);
		}
		for (int i = 0; i < n; i++)
		{
			result[i] = 1;
			for (int j = i - 1; j >= 0; j--)
			{
				if (num[i]>num[j] && result[i] < (result[j] + 1))
					result[i] = result[j] + 1;
			}
		}

		int max = -1;
		for (int i = 0; i < n; i++)
		{
			if (result[i]>max)
			{
				max = result[i];
			}
		}
                 result.clear();
                num.clear();
		result1.push_back(max);
	}
	for (int i = 0; i < result1.size(); i++)
	{
		cout << result1[i] << endl;
	}
}

编辑于 2016-08-29 13:31:36 回复(2)
Beannn头像 Beannn 
第一种方法最普通的方法dp
#include <stdio.h>

int d[3005];

int dp(int a[], int n)
{
	int i, j;
	int tmp;
	int max=1;
	for(i=0;i<n;i++)
	{
		d[i]=1;
		for(j=i-1;j>=0;j--)
		{
			if(a[j]<a[i])
			{
				tmp=d[j]+1;
				if(tmp>d[i])
					d[i]=tmp;
			}		
		}
		if(d[i]>max)
			max=d[i];
	}
	return max;
}

int main()
{
	int i;
	int n,k;
	int a[3005];
	scanf("%d", &n);
	while(n--)
	{
		scanf("%d", &k);
		for(i=0;i<k;i++)
			scanf("%d", a+i);
		printf("%d\n",dp(a,k));	
	}
	return 0;
}

//第二种方法qsort+LCS,但是通过不了，因为内存超过限制
#include <stdio.h>
#include <string.h>

void swap(int*arr, int i, int j)
{
	int tmp = arr[i];
	arr[i]=arr[j];
	arr[j]=tmp;
}

void qsort(int s[], int l, int r)
{
	if(l<r)
	{
		int i=l;
		for(int j=i+1;j<=r;j++)
			if(s[j]<s[l])
				swap(s,++i,j);
		swap(s,i,l);
		qsort(s,l,i-1);
		qsort(s,i+1,r);
	}
}

int dp[3005][3005];
int a[3005],b[3005];

int LCS(int s[], int sc[], int len)
{
	for(int i=1; i<=len;i++)
		for(int j=1;j<=len;j++)
		{
			if(s[i-1] == sc[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
			else if(dp[i-1][j]>dp[i][j-1])
				dp[i][j]=dp[i-1][j];
			else 
				dp[i][j]=dp[i][j-1];
		}
		
	return dp[len][len];
}

int main()
{
	int i;
	int n,k;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%d", &k);
		for(i=0;i<k;i++)
			scanf("%d", a+i);
			memcpy(b,a,sizeof(int)*k);
		qsort(b,0,k-1);
		printf("%d\n",LCS(a,b,k));	
	}
	return 0;
}

发表于 2016-05-09 21:14:51 回复(2)
名俗人头像 名俗人

动态规划题，一般先写出问题的最优子结构的关系式，如下：
d[n] = max{ d[i]+1 | a[i] < a[n], 0 =< i <= n }
其中，a[i]表示数组下标为i的数，d[i]表示以a[i]为结尾的递增序列的长度。
很明显，数组的最长递增子序列的长度为d[0]到d[n]中的一个值

代码如下： 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            int[] array = new int[n];
            for (int j = 0; j < n; j++) {
                array[j] = scanner.nextInt();
            }
            int len = getLisLen(array, n);
            System.out.println(len);
        }

        scanner.close();
    }

    public static int getLisLen(int[] array, int n) {
        int[] d = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            d[i] = 1;
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    d[i] = Integer.max(d[i], d[j]+1); 
                }
            }
            max = Integer.max(max, d[i]);
        }
        return max;
    }
}

编辑于 2018-06-28 19:14:23 回复(2)
selfboot头像 selfboot 

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
    int T;
    cin  >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> nums(n, 0);
        for(int i=0;i<n;i++){
            cin >> nums[i];
        }
        vector<int> keep;
        for(int i=0;i<n;i++){
            auto it = lower_bound(keep.begin(), keep.end(), nums[i]);
            if(it!=keep.end()){
                *it = nums[i];
            }
            else{
                keep.push_back(nums[i]);
            }
        }
        cout << keep.size() << endl;
    }
    return 0;
}

发表于 2016-05-04 14:04:00 回复(0)
哈哈哈啥啥啥头像 哈哈哈啥啥啥 
import java.util.Scanner;

public class Main {
    private static int[] getdp1(int[] arr) {
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }

    private static int generateLIS(int[] arr, int[] dp) {
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int T = in.nextInt();
            for (int i = 0; i < T; i++){
                int n = in.nextInt();
               	int[] a = new int[n];
                for(int j = 0; j < n; j++){
                    a[j] = in.nextInt();
                }
                int[] dp = getdp1(a);
        		System.out.println(generateLIS(a, dp));
            }
        }
      	
    }
}

编辑于 2017-02-15 18:17:26 回复(0)
MrB头像 MrB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
using namespace std;

int getLIS(vector<int> A, int n) {
    //数组dp[i]表示必须以arr[i]这个数字结尾情况下的arr[0...,i-1]中的最长上升子序列的长度
    int dp[n];
    dp[0] = 1;
    int res = 1;
    //状态方程为dp[i] = max{dp[j]+1 (0<=j<i,arr[j]<arr[i])}
    for (int i = 1; i < n; i++)
    {
  
        int max = 0;
        for (int j = i - 1; j >= 0; --j)
        {
            if (A[j] < A[i] && dp[j] > max) {
                max = dp[j]; //不断更新max数值
            }
        }
        dp[i] = max + 1;
        res = max + 1 > res? max + 1:res; //更新res数值
    }
    return res;
}

int main()
{
    int times;
    cin >> times;
    //定义一个数组,用于保存每组数据的输出结果。而不是输入一组数据,输出一个结果。
    vector<int> result;
    for (int index = 0; index < times; index++) {
        
        int sizeOfnumber;
        cin >> sizeOfnumber;
        vector<int> vec;
        for (int j = 0; j < sizeOfnumber; j++) {
            int number;
            cin >> number;
            vec.push_back(number);
        }
        
        int temp =  getLIS(vec,sizeOfnumber);
        result.push_back(temp);
    }
    
    
    for (int index = 0; index < result.size(); index++) {
        cout << result[index] << endl;
    }
}
发表于 2016-09-07 22:47:38 回复(0)
cainiaoed头像 cainiaoed
//找最长递增子序列（即找后一个元素比前一个元素大的这么一个序列（找出比自己小的并且看它在它序列的位置，比它的位置+1），并统计每个元素的递增子序列的长度，最后得出最长递增序列）
import java.util.Scanner;

public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int T=in.nextInt();
for(int i=0;i<T;i++){
int N=in.nextInt();
int[] a=new int[N];
for(int j=0;j<N;j++){
a[j]=in.nextInt();
}
int[] count=new int[N];
for(int k=0;k<N;k++){
count[k]=1;
for(int l=0;l<k;l++){
if(a[l]<a[k]&&count[l]+1>count[k])
count[k]=count[l]+1;
}
}
int max=0;
for(int s=0;s<N;s++){
if(count[s]>max){
max=count[s];
}
}
System.out.println(max);
}
} 
}

编辑于 2016-05-04 11:49:04 回复(0)
牛客909508号头像 牛客909508号 
#include<iostream> using namespace std;
int getMaxLength(int A[], int N)
{
 int max = 1;
 int *length = new int[N];
 for(int i = 0; i < N; i++)
 {
  length[i] = 1;
  for(int j = i-1; j >= 0; j--)       //获得第i个元素能够得到的最大长度 
  {
   if(A[i] > A[j])
   {
    int temp = length[j] + 1;
    if(length[i] < temp)
    length[i] = temp;
   }
  }
  if(length[i] > max)      //get max length
  max = length[i];
 }
 delete []length;
 return max; 
}
int main()
{
 int T;
 int N;
 cin>>T;
 while(T--)
 {
  cin>>N;
  int *A = new int[N];
  for(int i = 0; i < N; i++)
  {
   cin>>A[i];
  }
  cout<<getMaxLength(A, N)<<endl;
  delete []A;
 }
 return 0; 
}

发表于 2016-06-22 11:48:43 回复(0)
醉清风951头像 醉清风951 
#include "iostream"
using namespace std;
 
int main(){
    int T,N,i,j;
    int a[3005] = {0};
    int dp[3005] = {0};
    cin>>T;
    while(T--){
        int count = 0;
        cin>>N;
        for(i = 0;i < N; i++)
            cin>>a[i];
        for(i = 0;i < 3005; i++)
            dp[i] = 1;
        for(i = 0;i < N; i++)
            for(j = i + 1;j < N; j++){
                if(a[i] < a[j]){
                    dp[j] = max(dp[j],dp[i]+1);
                }
            }
        int Max = 0;
        for(i = 0;i < N; i++){
            if(dp[i] > Max)
                Max = dp[i];
        }
        cout<<Max<<endl;
    }
    return 0;
}

发表于 2019-09-18 15:14:03 回复(0)
Python
牛客156465号头像 牛客156465号
def compute_sub_max(num_list):
    result_list = [1]
    for i, one_num in enumerate(num_list[1:]):  # 找到以第i个位置结尾的最长子串长度
        i += 1
        max_len = 1
        while i >= 0:
            if num_list[i] < one_num:
                max_len = max(max_len, result_list[i] + 1)
            i -= 1
        result_list.append(max_len)
    return max(result_list)

num_group = int(raw_input())
while num_group > 0:
    raw_input()
    print compute_sub_max(map(int, raw_input().split()))
    num_group -= 1
发表于 2019-04-14 17:25:02 回复(0)
我算哪块小饼干头像 我算哪块小饼干 

	package coding_test;





	







	import java.io.BufferedReader;





	import java.io.IOException;





	import java.io.InputStreamReader;





	import java.util.Arrays;





	







	public class LongestIncreasingSubSequence {





	







	    public static int logSeq(int[] seq) {





	        int[] f = new int[seq.length];





	        f[0] = 1;





	        for(int i = 1; i < seq.length; i++) {





	            f[i] = 1;





	            for(int j = 0; j < i; j++) {





	                if(seq[i] > seq[j] && f[i] <= f[j]) {





	                    f[i] = f[j] + 1;





	                }





	            }





	        }





	        





	        int maxLength = -1;





	        for(int i = 0; i < f.length; i++) {





	            if(maxLength < f[i]) {





	                maxLength = f[i];





	            }





	        }





	        return maxLength;





	    }





	    





	    public static void main(String[] args) {





	         try {  





	             





	                BufferedReader strin=new BufferedReader(new InputStreamReader(System.in)); 





	                System.out.print("请输入组数：");  





	                String group_numb = strin.readLine(); 





	                int numb = Integer.parseInt(group_numb); //number of groups





	                int[][] arr = new int[numb][]; // all group arrays





	                int [] length = new int[numb]; //each group length





	                int k =1, j=0;





	                while(numb > 0) {





	                        System.out.print("请输入第"+k+"组长度：");                     





	                        length[j] = Integer.parseInt(strin.readLine());





	                        System.out.print("请输入第"+k+"组数据：");                   





	                        String[] string = strin.readLine().split(" ");





	                        arr[j] = new int[length[j]];





	                        for(int i=0; i<string.length;i++) {





	                            arr[k-1][i] = Integer.parseInt(string[i]);





	                        }





	//                        for(int[] a:arr) {





	//                            System.out.println(Arrays.toString(a));





	//                        }





	                        k++;





	                        numb--;





	                        j++;





	                }





	                int m = 0;





	                //j is equal to the original numb





	                while(j > 0) {





	                        System.out.print("第"+ (m+1) +"组最长递增子序列的长度：" + logSeq(arr[m])+"\n");           





	//                        System.out.println(logSeq(arr[m]));





	                        m++;





	                        j--;





	                }





	                             





	            } catch (IOException e) {  





	                e.printStackTrace();  





	            }  





	    }





	}

发表于 2019-04-03 15:54:10 回复(0)
牛客1659416头像 牛客1659416
动态规划 

	#include <iostream>





	usingnamespacestd;





	 





	intmain()





	{





	    intT;





	    while(cin>>T)





	    {





	        for(inti=0; i<T; i++)





	        {





	            intN;





	            cin>>N;





	            intarr[N],dp[N];





	            for(intj=0; j<N; j++)





	            {





	                cin>>arr[j];





	                dp[j]=1;





	            }





	            intmax=1;





	            for(intk=1; k<N; k++)





	            {





	                for(inth=0; h<k; h++)





	                {





	                    if(arr[h]<arr[k])





	                    {





	                        if(dp[h]+1>dp[k])





	                            dp[k]=dp[h]+1;





	                    }





	                }





	                if(dp[k]>max)





	                    max=dp[k];





	            }





	            cout << max << endl;





	        }





	    }





	    return0;





	}

发表于 2018-04-27 17:30:30 回复(0)
口可口可头像 口可口可
存储，数组每一位的最长路径和，节点位置
发表于 2017-09-15 17:30:35 回复(0)
PowerLaser头像 PowerLaser
复杂度o(N2)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int num,x;
cin>>num;
vector<vector<int>> data(num);
vector<vector<int>> dp(num);
for(int i=0;i<num;i++){
cin>>x;
data[i].resize(x);
dp[i].resize(x);
for(int j=0;j<x;j++) cin>>data[i][j];
}

for(int i=0;i<num;i++){
for(int j=0;j<data[i].size();j++){
dp[i][j]=1;
for(int k=0;k<j;k++){
if(data[i][k]<data[i][j]) dp[i][j]=max(dp[i][j],dp[i][k]+1);
}
}
}
for(int i=0;i<num;i++) cout<<*max_element(dp[i].begin(),dp[i].end())<<endl;
return 0;
}
发表于 2017-08-30 17:15:31 回复(0)
Jimmy_gg头像 Jimmy_gg 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
int findLongest(vector<int> A, int n) {
	// write code here
	if (!n)
		return 0;
	vector<int> dp(n, 1);
	multiset<int> help;
	help.insert(A[0]);
	for (int i = 1; i < n; i++) {
		multiset<int>::iterator itor = help.lower_bound(A[i]);
		if (itor != help.end()) {
			help.erase(itor);
			help.insert(A[i]);
			int num = 1;
			multiset<int>::iterator iter = help.begin();
			for (; iter != help.end(); iter++) {
				if (*iter == A[i])
					break;
				num++;
			}
			dp[i] = num;
		}
		else {
			help.insert(A[i]);
			dp[i] = help.size();
		}
	}
	int length = dp[0];
	for (int i = 1; i < n; i++) {
		if (length < dp[i]) {
			length = dp[i];
		}
	}
	return length;
}
int main() {
	using namespace std;
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> height(n);
		for (int i = 0; i < n; i++) {
			cin >> height[i];
		}
		cout << findLongest(height, n) << endl;
	}
	return 0;
}

发表于 2017-06-16 09:08:25 回复(0)
蘅芜君头像 蘅芜君 
#include<iostream>
#include<vector>
using namespace std;
using std::vector;

int main(void){
    int times;
    int T;
    cin >> times;
    for(int q = 0; q < times; q++){
        cin >> T;
    	vector<int> a;
        vector<int> nn(T, 1);
        int temp = 0;
        int lm = 1;
    	for(int i = 0; i < T; i++){
        	cin >> temp;
        	a.push_back(temp);       
    	}
        
 		for(int i = 0; i < T - 1; i++){
        	for(int k = i; k >= 0; k--){
          	  if((a[i + 1] > a[k]) && (nn[i + 1] < nn[k] + 1))
                    nn[i + 1] = nn[k] + 1;
        	}
    	}
                
        for(int i = 0; i < T; i++)
        	if(lm < nn[i])  lm = nn[i];
    
   		cout << lm << endl;
    }   

   return 0;
}

发表于 2017-03-29 17:04:57 回复(0)
天才阿张头像 天才阿张
#include<vector>
#include<iostream>
using namespace std;
int func(vector<int> a, int l){

    vector<int> b(l,1);
    int max=1;
    for (int i=1;i<l;i++){
        for (int j=0;j<i;j++){
            if (a[i]>a[j] && b[j]+1>b[i])
                b[i]=b[j]+1;
            if (b[i]>max)
                max=b[i];
        }
    }
    return max;
}
int main(){
    int n;
    while(cin>>n){
        int l;
        for (int i=0;i<n;i++){
            cin>>l;
            vector<int> a(l);
            for (int j=0;j<l;j++){
                cin>>a[j];
            }
            int max=func(a,l);
            cout<<max<<endl;
        }
    }
    return 0;
}
发表于 2017-03-29 10:08:34 回复(0)
牛客126181号头像 牛客126181号
#include<iostream>
#include<stdlib.h>
using namespace std;
intintcmp(constvoid*a,constvoid*b)
{
 return*(int*)b-*(int*)a;
}
intfind(inta[],intn)
{
    intd[n];
 for(inti=0;i<n;i++)
   { 
     d[i]=1;
     for(intj=0;j<i;j++)
     {
      if(a[i]>a[j]&&d[j]+1>d[i])
          d[i]=d[j]+1; 
     }
     
   }
     qsort(d,n,sizeof(int),intcmp);
    returnd[0];
}
 
intmain()
{
    intd[3000];
    intm,n;
    cin>>m;
        while(m--)
  {
        cin>>n;
        for(intj=0;j<n;j++)
            cin>>d[j];
            cout<<find(d,n)<<endl;
  }
} 
发表于 2016-10-06 21:58:45 回复(0)
Java
ZhanHeng头像 ZhanHeng 
import java.util.*;

public class Main{
    public static int getLIS(int[] arr) {
		int[] dp = new int[arr.length];
		int[] ends = new int[arr.length];
		ends[0] = arr[0];
		dp[0] = 1;
		int right = 0;
		int l = 0 , r = 0 , m = 0;
		for (int i = 1; i < arr.length; i++) {
			l = 0;
			r = right;
			while (l <= r) {
				m = (l + r) / 2;
				if (arr[i] > ends[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			right = Math.max(right, l);
			ends[l] = arr[i];
			dp[i] = l + 1;
		}
        //以上是获取dp数组，引入辅助数组+二分查找，复杂度O(NlogN)
        int len = 0;
		for (int i = 0; i < dp.length; i++)
			if (dp[i] > len) 
				len = dp[i];
		return len;
	}

    public static void main(String[] args){
         Scanner in = new Scanner(System.in);
         while (in.hasNextInt()) {
            int t = in.nextInt();
            while(t--!=0){
               int n = in.nextInt();
               int[] arr = new int[n];
               for(int i=0 ; i<n ; i++){
                   arr[i] = in.nextInt();
               }
               System.out.println(getLIS(arr));
             }
        }
    }
}

编辑于 2016-09-07 23:32:46 回复(0)
松华皮蛋me头像 松华皮蛋me 
import java.util.Scanner;
 
public class  Main {
        public static  void main(String[] args){
                int len;
                Scanner in = new Scanner(System.in);
                while (in.hasNext()) {
                        int size = in.nextInt();
                        for(int i=0;i<size;i++) {
                            int len = in.nextInt();
                            int[] data = new int[len];
                            for(int j=0;j<len;j++){
                                data[j] = in.nextInt();
                            }
                            len = getDp(data);
                            System.out.println(len);
                        }
                    
                }
             
        }
 
        public static int getDp(int[] arr) {
                int[] dp = new int[arr.length];
                int[] end = new int[arr.length];
                end[0] = arr[0];
                dp[0] = 1;
                int l,r,m,right=0;
                for(int i=1;i<arr.length;i++) {
                        l = 0;
                        r = right;
                        while (l<=r) {
                                m = (l+r)/2;
                                if(arr[i]>end[m]) {
                                        l = m+1;
                                }
                                else {
                                        r = m-1;
                                }
                        }
                        right = Math.max(right,l);
                        end[l]= arr[i];
                        dp[i] = l+1;
                }
 			 int len = 0;
             for(int i=0;i<dp.length;i++) {
                 if(dp[i]>len) {
                     len = dp[i];
                 }
             }
            return len;
        }
 
}

发表于 2016-08-24 21:47:50 回复(0)
提交观点

问题信息

动态规划
来自：完美世界2016实习生笔试题
难度：
23条回答 16677浏览

热门推荐

通过挑战的用户

相关试题

最长递增子序列A

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号