小明爬山(最长上升子序列)

2023-11-20 12:59

本文主要是介绍小明爬山(最长上升子序列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

小明爬山(最长上升子序列)

  • 问题描述
  • 算法思路
  • 代码

问题描述

问题描述
你有个同学叫小明,他早听闻祖国河山秀丽,于是有一个爬山的计划,并列了一张所有山的高度表,而又因“人往高处走”的说法,所以他希望爬的每一座山都比前一座要高,并且不能改变山的高度表上的顺序,爬的山数还要最多,请贵系的你帮他解决这个问题。

输入格式

输入第一行为num,代表山的个数   输入第二行有num个整数,代表每座山的高度

输出格式

输出只有一个数,为符合要求的最大爬山数

样例输入

10 1 3 5 7 9 2 4 6 8 10

样例输出

6

(样例说明:选择1 3 5 7 8 10)

样例输入

10 1 3 2 7 5 4 5 6 10 11

样例输出

7

(样例说明:选择1 2 4 5 6 10 11)

数据规模和约定

对于100%的数据,num <= 100000,高度<=10000。

算法思路

choise[i]存放以arr[i]结尾的最长上升子序列的长度

  chose[i]=Math.max(chose[i],chose[j]+1);  //chose[i]  num

在这里插入图片描述

代码

import java.util.Arrays;
import java.util.Scanner;/*** @author admin*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();int[] arr = new int[num];int[] chose = new int[num];for (int i = 0; i < num; i++) {arr[i] = scanner.nextInt();}Arrays.fill(chose,1);for (int i = 1; i < num; i++) {for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) {chose[i]=Math.max(chose[i],chose[j]+1);}}}Arrays.sort(chose);System.out.println(chose[num-1]);
}}

但是时间复杂度达到了O(n²),导致了只通过了四个测试点
在这里插入图片描述

优化的还在想,后续。。。。

这篇关于小明爬山(最长上升子序列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/394770

相关文章

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],