首页 > 试题广场 >

最长上升子序列

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

热度指数：5634 时间限制：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

算法知识视频讲解

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)

Java

落尘QAQ

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()){
            int n = scan.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++){
                arr[i] = scan.nextInt();
            }
            System.out.println(func(arr,n));
        }
    }
    public static int func (int[] arr,int n){
        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 (arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            if (dp[i] >= max){
                max = dp[i];
            }
        }
        return max;
    }
}

发表于 2021-07-28 21:46:44 回复(0)

Java

安徒生的谎言

import java.util.Arrays;
import java.util.Scanner;

public class LongestIncreaseSub {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int[] nums=new int[n];
            for(int i=0;i<n;i++) {
                nums[i]=sc.nextInt();
            }
            int[] dp=new int[n];
            for(int i=0;i<n;i++) {
                dp[i]=1;
            }
            for(int i=1;i<n;i++) {
                for(int j=0;j<i;j++) {
                    if(nums[i]>nums[j]) {
                        dp[i]=Math.max(dp[j]+1, dp[i]);
                    }
                }
            }
            Arrays.sort(dp);
            System.out.println(dp[n-1]);
        }
    }
}

发表于 2018-01-26 14:18:54 回复(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)