首页 > 试题广场 >

最长递增子序列B

[编程题]最长递增子序列B

热度指数：1766 时间限制：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<=T<=20,1<=N<=3000,0<=ai<=MAX_INT.

示例1

输入

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

输出

1 46 78
6 8 17

算法知识视频讲解

OnePiece~~

#include<iostream>
#include<vector>
using namespace std;
intmain(){
    intn;
    while(cin>>n){
        for(intm=0;m<n;m++){
            intsize,max=0,lastpos;
            cin>>size;
            vector<int>array(size);
            for(intj=0;j<size;j++){
                cin>>array[j];
            }
            vector<int> dp(size);
            vector<int> pos(size);
            for(inti=0;i<size;i++){
                dp[i]=1;
                for(intj=0;j<i;j++){
                    if(array[i]>array[j]){
                        if(dp[j]+1>dp[i]){
                            dp[i]=dp[j]+1;
                            pos[i]=j;
                        }
                        if(max<dp[i]){
                            max=dp[i];
                            lastpos=i; 
                        }  
                    }
                }
            }
            vector<int>ans;
            for(inti=0;i<max;i++){
                ans.push_back(array[lastpos]);
                lastpos=pos[lastpos];
            }
            for(inti=max-1;i>=1;i--)
                cout<<ans[i]<<' ';
            cout<<ans[0]<<endl;
        }
    }
    return0;
}

编辑于 2016-08-07 16:16:27 回复(0)

bloodycoder

这个题用dp，跟最长子序列差不多，只是要记录一下上一个点的位置。

这个算法复杂度o(n^2).如果用排序可以优化到o(nlog(n))

#include <iostream>
#include <string.h>
using namespace std;
struct saveT{
	int longest; //储存以这个数为尾的最长子序列的长度
	int last_point;//上一个点
};
int main(){
	int t,n,array[3005],max_num,last_item,answer[3005];
	saveT save[3005];
	memset(save,0,sizeof(save));
	cin>>t;
	for(int i=0;i<t;i++){
		max_num = last_item = 0;
		cin>>n;
		for(int j=0;j<n;j++){
			cin>>array[j];
		}
		for(int j=0;j<n;j++){
			save[j].longest = 1;
			save[j].last_point = j;
			for(int k=0;k<j;k++){
				if(array[j]>array[k]){ //找这个元素之前的，如果自己比他大
					if(save[k].longest+1>save[j].longest){//并且他的最长子序列加1 比自己长
						save[j].longest = save[k].longest+1;
						save[j].last_point = k;
						if(max_num<save[j].longest){
							max_num = save[j].longest;
							last_item = j;
						}
					}
				}
			}
		}
		for(int j=0;j<max_num;j++){
			answer[j] = last_item;
			last_item = save[last_item].last_point;
		}
		for(int j=max_num-1;j>0;j--){
			cout<<array[answer[j]]<<" ";
		}
        cout<<array[answer[0]]<<endl;
	}
}

编辑于 2016-05-16 11:41:18 回复(1)

JavaScript

小太阳照亮明天

发表于 2018-08-29 19:31:09 回复(0)

牛客1659416

还是动态规划，只不过要记录下最长子序列


	#include <iostream>



	#include <vector>



	 



	usingnamespacestd;



	 



	intmain()



	{



	    intT;



	    while(cin>>T)



	    {



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



	        {



	            intN;



	            cin>>N;



	            intarr[N],dp[N];



	            vector<vector<int> > vi(N);



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



	            {



	                cin>>arr[j];



	                dp[j]=1;



	                vi[j].push_back(arr[j]);



	            }



	            intidx=0;



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



	            {



	                inttemp=k;



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



	                {



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



	                    {



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



	                        {



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



	                            temp=h;



	                        }



	                    }



	                }



	                if(temp<k)



	                    vi[k].insert(vi[k].begin(),vi[temp].begin(),vi[temp].end());



	                if(vi[k].size()>vi[idx].size())



	                {



	                    idx=k;



	                }



	            }



	            for(ints=0; s<vi[idx].size()-1; s++)



	                cout << vi[idx][s] << " ";



	            cout << vi[idx][vi[idx].size()-1] << endl;



	        }



	    }



	    return0;



	}

发表于 2018-04-27 17:31:57 回复(0)

Jimmy_gg

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
vector<int> findLongestArr(vector<int> A, int n) {
	// write code here
	vector<int> ans;
	if (!n)
		return ans;
	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];
	int beg = 0;
	for (int i = 1; i < n; i++) {
		if (length < dp[i]) {
			length = dp[i];
			beg = i;
		}
	}
	ans.insert(ans.begin(), A[beg]);
	length = length - 1;
	while (length--) {
		int i = 0;
		while (i < beg) {
			if (dp[i] == dp[beg] - 1 && A[i] < A[beg]) {
				ans.insert(ans.begin(), A[i]);
				beg = i;
				break;
			}
			i++;
		}
	}
	return ans;
}
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];
		}
		vector<int> ans;
		ans = findLongestArr(height, n);
		for (int i = 0; i < ans.size() - 1; i++) {
			cout << ans[i] << " ";
		}
		cout << ans[ans.size() - 1] << endl;
	}
	return 0;
}

发表于 2017-06-16 09:22:22 回复(0)

喜欢兰花山丘

"长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6"

其实应该输出 {1,3,5,6,7,8}吧, 题目没有约定输出顺序, 测试数据很难统一

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

什么???

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

using namespace std;

vector<int> dp(vector<int> seq){
	int max = 0;
	int maxpos = -1;
	int size = seq.size();
	vector<int> rec(size, 1);
	vector<int> from(size, -1);
	for (int i = 0; i < size; i++){
		for (int j = 0; j < i; j++){
			if (seq[i] > seq[j] && rec[j] + 1 > rec[i]){
				rec[i] = rec[j] + 1;
				from[i] = j;
				if (rec[i] > max){
					maxpos = i;
					max = rec[i];
				}

			}
		}
	}

	vector<int> ret;

	int curr = maxpos;

	while (curr >= 0){
		ret.push_back(seq[curr]);
		curr = from[curr];
	}
	reverse(ret.begin(),ret.end());
	return ret;
}

int main(){
	int sets;
	cin >> sets;
	for (int i = 0; i < sets; i++){
		int nums;
		cin >> nums;
		vector<int> raw(nums);
		for (int j = 0; j < nums; j++){
			cin >> raw[j];
		}
		vector<int> result = dp(raw);
		for (int j = 0; j < result.size() - 1; j++){
			cout << result[j] << " ";
		}
		cout << result[result.size() - 1] << endl;
	}
	return 0;
}

发表于 2016-08-27 20:35:27 回复(0)

gloomy

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

public class Main {
	public static void main(String[] args) {
		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();
				}
				getMaxIncrementSequence(data, len);
			}
		}
		in.close();
	}

	public static void getMaxIncrementSequence(int[] data, int len) {
		int[] dp = new int[len];
		dp[0] = 1;
		int max = 1;
		List<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		int index = -1, k = 0;
		ArrayList<Integer> tem = new ArrayList<Integer>();
		tem.add(data[0]);
		res.add(tem);
		for (int i = 1; i < len; i++) {
			index = -1;
			tem = new ArrayList<Integer>();
			for (int j = 0; j < i; j++) {
				if (data[i] > data[j] && dp[j] > dp[i]) {
					dp[i] = dp[j];
					index = j;
				}
			}
			++dp[i];
			if (index > -1) {
				tem.addAll(res.get(index));
			}
			tem.add(data[i]);
			res.add(tem);
			if (dp[i] > max) {
				max = dp[i];
				k = i;
			}
		}
		tem = res.get(k);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < tem.size() - 1; i++) {
			sb.append(tem.get(i));
			sb.append(" ");
		}
		sb.append(tem.get(tem.size() - 1));
		System.out.println(sb.toString());
	}
}

发表于 2016-07-30 14:36:39 回复(0)

jacke

public static ArrayList<Integer> lisB(int[] array) { //dp时间复杂度（o(n2)）
        ArrayList<Integer> result = new ArrayList<>();
        if(array == null || array.length == 0) return result;
        int length = array.length;
        ArrayList<ArrayList<Integer>> buffer = new ArrayList<>();//每个索引下的最大子序列长度列

        for(int i = 0; i < length; i++) {
           ArrayList<Integer> temp = new ArrayList<>();
           temp.add(array[i]);
           buffer.add(temp);
           for(int j = i - 1; j >= 0; j--) {


               if(array[i] > array[j] && buffer.get(i).size() <= buffer.get(j).size()) { //j < i && array[j] < array[i]
                   buffer.set(i,new ArrayList<Integer>(buffer.get(j)));   //
                    buffer.get(i).add(array[i]);
               }

           }
           if(result.size() < buffer.get(i).size()) {
               result = buffer.get(i);
           }
        }
        return result;

   }

发表于 2016-07-24 10:44:40 回复(0)

come_on_baby

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;

//求一列数中最长的等差数列，如3，4，5，8，9，10，2，则输出4.
public class Longseq {

    public static int maxNumseq(Integer[] data)
    {
    int max=2,maxindex=0,maxstep;


    Arrays.sort(data);

    int findex,step,count;
    for(int i=0;i<data.length-2;i++)
    {
      findex=i+1;
      step=data[i+1]-data[i];
      count=2;
      for(int j=i+2;j<data.length;j++)
      {
       if(data[j]==data[findex] +step)
       {
        count++;
        findex=j;
       }
      }

      if(count>max)
      {
       max=count;
       maxindex=i;
       maxstep=step;
      }
    }

    return max;
    }

    public static void main(String s[])
{
  int a,b;
  Scanner sc=new Scanner(System.in);
  Vector<Integer> v=new Vector();
  int num=sc.nextInt();
  while(num>0)
  {
   v.add(sc.nextInt());
   num--;
  }

  System.out.println( maxNumseq( v.toArray(new Integer[0])) );

}
}

发表于 2016-05-16 17:44:03 回复(0)

selfboot

#include <iostream>
#include <vector>
#include <set>
 
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;
        vector<set<int>> pos;
        for(int i=0;i<n;i++){
            auto it = lower_bound(keep.begin(), keep.end(), nums[i]);
            if(it!=keep.end()){
                (pos.begin() + (it-keep.begin()))->insert(i);
                *it = nums[i];
            }
            else{
                pos.push_back({i});
                keep.push_back(nums[i]);
            }
        }
        vector <int> ans;
        for(auto iter = pos.rbegin(); iter!=pos.rend(); iter++){
            const set<int> &tmp = *iter;
            if(ans.empty()){
                ans.push_back(*tmp.begin());
            }
            else{
                for(const auto &t : tmp){
                    if (nums[t]<nums[ans.back()]){
                        ans.push_back(t);
                        break;
                    }
                }
            }
        }
        for(auto iter = ans.rbegin(); iter!=ans.rend(); iter++){
            cout << nums[*iter];
            if(iter+1 != ans.rend())    cout << " ";
        }
        if(T)   cout << endl;
    }
    return 0;
}

发表于 2016-05-04 14:07:31 回复(0)