Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？
数据范围：每组数据长度满足 
， 数据大小满足 
[编程题]Redraiment的走法
- 热度指数：184662 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度
输出描述:
输出一个结果
示例1
输入
6 2 5 1 5 4 5
输出
3
说明
6个点的高度各为 2 5 1 5 4 5 如从第1格开始走,最多为3步, 2 4 5 ，下标分别是 1 5 6 从第2格开始走,最多只有1步,5 而从第3格开始走最多有3步,1 4 5， 下标分别是 3 5 6 从第5格开始走最多有2步,4 5， 下标分别是 5 6 所以这个结果是3。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
int max=0;
int[] DP=new int[n];
for(int i=0;i<n;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);
}
}
max=Math.max(max,DP[i]);
}
System.out.println(max);
}
}
发表于 2023-09-09 21:13:02
回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] str = null;
while (sc.hasNext()) {
sc.nextLine();
str = sc.nextLine().split(" ");
}
/*int[] intChar = Arrays.stream(str)//通过流来处理str
.mapToInt(Integer::parseInt).
toArray();
//流处理方法,忘得差不多了,不看了就先,先做题在说
*/
int[] hight = new int[str.length];//定义一个数组存放梅花桩高度
for (int i = 0; i < str.length; i++) {
hight[i] = Integer.parseInt(str[i]);
}
//定义一个数组用来存放在以第i个桩为终点时,前面的最长递增子序列
int[] num = new int[hight.length];
Arrays.fill(num, 1);//用1初始化num数组
for (int i = 1; i < hight.length; i++) {//i代表以i为终点也能以0为起点开始算终点,但是意义
for (int j = 0; j < i; j++) {//j代表i前面的任意点,那么num[j]就是当前
//从0开始计算,如果j比i低了,那么就代表i多了个解法
//i的最大上升子序列是在自己前面,比自己低的点的最大上升子序列+1
if ((hight[i] > hight[j])//如果i点位置比j高,
&& (num[j] >= num[i])) //并且此时记录的j点的最大步数多于或等于此时记录的i点的最大步数
num[i] = num[j] + 1;
}
}
Arrays.sort(num);
System.out.println(num[num.length-1]);//没有注释的代码就是依托带边,我**自己都看不懂
}
编辑于 2023-02-24 16:44:05
回复(0)
动态规划求最长递增子序列
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 获取输入的梅花桩个数
int n = in.nextInt();
// 定义一个数组，用于存放梅花桩的高度
int[] hight = new int[n];
// 获取输入的梅花桩高度
for (int i = 0; i < n; i++) {
hight[i] = in.nextInt();
}
// 定义一个数组，用于存放第i个梅花桩时，前面可生成的递增最长子序列个数
int[] dp = new int[n];
// 将dp最长默认全部赋值为1
Arrays.fill(dp, 1);
// 定义一个变量，表示第i个木桩前面的最长递增子序列个数,默认为1个,及求dp数组中的最大值
int max = 1;
// 利用动态规划求第i个木桩的最长递增子序列，最需要求得第i个木桩最长的递增子序列后加上1就OK
for (int i = 1 ; i < n; i++) {
for (int j = 0 ; j < i; j++) {
if (hight[i] > hight[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(dp[i], max);
}
// 输出结果
System.out.println(max);
}
}
发表于 2023-02-14 10:04:08
回复(0)
// 6 // 2 5 1 5 4 5 // 0 1 2 3 4 5 // dp[i] 表示以i为结尾的最长子序列的长度 // 当只有一个元素 [2] // dp[0]=1 // 加入元素5 ,[2,5] // dp[0]=1 ,d[1]=d[0]+1=2 5比2大,所以可以在2的基础上加 // 加入元素1 ,[2,5,1] // dp[0]=1 ,d[1]=2 d[2]=1 // 加入元素5 ,[2,5,1,5] // dp[0]=1 ,d[1]=2 d[2]=1, d[3]=max{d[0]+1,d[2]+1}=2 // 加入元素4 ,[2,5,1,5,4] // dp[0]=1 ,d[1]=2 d[2]=1, d[3]=2, d4=max{d[0]+1,d[2]+1,}=2 // 加入元素5 ,[2,5,1,5,4,5] // dp[0]=1 ,d[1]=2 d[2]=1, d[3]=2, d[4]=2,d5=max{d[0]+1,d[2]+1,d[4]+1}=3 // dp[0]=1 ,d[1]=2 d[2]=1, d[3]=2, d[4]=2,d[5]=3 }
发表于 2023-02-03 10:57:19
回复(1)
import java.util.Arrays;
import java.util.Scanner;
public class HJ103_dp最长增子序列 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] high=new int[n];
int[] dp=new int[n];
Arrays.fill(dp, 1);
for (int i = 0; i <n; i++) {
high[i]=sc.nextInt();
}
int max = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if(high[j]<high[i]){
dp[i]= Math.max(dp[i],dp[j]+1);
max=Math.max(dp[i],max);
}
}
}
System.out.println(max);
}
}
发表于 2022-08-26 15:38:37
回复(0)
带注释版的 动态规划 和 二分法 两种 方法
/**
* @author YXQ
* @create 2022/8/25 15:04
*/
import java.util.Arrays;
import java.util.Scanner;
/**
* Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？
* 输入描述：
* 数据共2行，第1行先输入数组的个数，第2行再输入梅花桩的高度
* 输出描述：
* 输出一个结果
*/
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for (int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
// System.out.println(findRedraiment(n,arr));
System.out.println(find(n,arr));
}
// 方法2.二分+贪心 dp[i]数组用来存长度为i+1的尽可能小的值
// *****但是注意 这个dp数组并不是走的路径（因为会存在从右向左走的情况），但是长度和路径长度一样
public static int find(int n,int[] arr){
int[] dp=new int[n];
dp[0]=arr[0];
int index=0;
for (int i=1;i<n;i++){
// 如果arr[i]大于dp中最大的值，则直接在dp后面加一位
if(dp[index]<arr[i])dp[++index]=arr[i];
// 如果arr[i]<=dp[len],则替换掉第一个大于等于arr[i]的数 利用二分法在dp中找到这个数
// 左闭右开型的二分法
else{
int l=0,r=index;
while (l<r){
int mid=l+(r-l)/2;
if(dp[mid]>=arr[i])r=mid;
else l=mid+1;
}
dp[r]=arr[i];
}
System.out.println();
}
return index+1;
}
// 方法1.直接动态规划
public static int findRedraiment(int n,int[] arr){
int[] dp=new int[n];
int res=0;
Arrays.fill(dp,1);
for (int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(arr[j]<arr[i])dp[i]=Math.max(dp[i],dp[j]+1);
if(dp[i]>res)res=dp[i];
}
}
return res;
}
}
发表于 2022-08-25 16:39:40
回复(0)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str =null;
String s =null;
while((s=br.readLine())!=null){
str=br.readLine();
System.out.println(dealString(str));
}
}
public static int dealString(String str){
ArrayList<Integer> al = new ArrayList();
int max=0;
String[] strs= str.split(" ");
for(int i = 0;i < strs.length;i++){
al.add(Integer.parseInt(strs[i]));
}
int[] dp = new int[al.size()];
for(int i = 0;i < al.size();i++){
dp[i] =1;
for(int j = 0;j<i;j++){
if(al.get(i)>al.get(j)){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
for(int i = 0 ; i < dp.length;i++){
if(dp[i]>max){
max = dp[i];
}
}
return max;
}
}
发表于 2022-05-04 21:49:56
回复(0)
使用两个下标i,j（j<i）计算数组arr 与 对应dp的值；如果arr[i] > arr[j] 的时候；计算dp[i] 此时 dp[i] = Math.max(dp[i], dp[j]+1)；
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int[] dp = new int[n];
Arrays.fill(dp, 1); // 初始化为1
int max = 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);
max = Math.max(dp[i], max);
}
}
}
System.out.println(max);
}
}
发表于 2022-05-03 18:13:06
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
count(arr);
}
}
private static void count(int[] arr) {
int[] countArr = new int[arr.length];
Arrays.fill(countArr, 1);
int max = 1;
// 以索引1结尾，求最长子序列，存入countArr[1]
// 当以2结尾时，就可以取1的最长子序列作为参考(这就是动态规划的核心-取前面的累计值作为参考)
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
// countArr[j]表示目前截止j处最长子序列，那么countArr[i]最长就是countArr[j]，
// 而arr[j] < arr[i]，那么countArr[i]就+1，反之countArr[i]不变
countArr[i] = Math.max(countArr[j] + 1, countArr[i]);
}
max = Math.max(max, countArr[i]);
}
}
System.out.println(max);
}
}
发表于 2022-04-09 19:52:52
回复(0)
// 动态规划
import java.util.*;
public class Main{public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sum = sc.nextInt();
int[] num = new int[sum];
for(int i=0;i<sum;i++){
num[i] = sc.nextInt();
}
int[] dp = new int[sum];
Arrays.fill(dp,1);
for(int i=1;i<sum;i++){
for(int j=0;j<i;j++){
if(num[j]<num[i]) dp[i] = Math.max(dp[i],dp[j]+1);
}
}
int max = 1;
for(int i:dp){
max = Math.max(max,i);
}
System.out.println(max);
}
}
发表于 2022-04-09 17:08:24
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int cnt = in.nextInt();
int[] arr = new int[cnt];
for (int i = 0; i < cnt ; i++) {
arr[i] = in.nextInt();
}
int a = maxLen2(arr);
System.out.println(a);
}
}
private static int maxLen2(int[] arr) {
int len = arr.length;
int[] dp = new int[len];
int max = 0;
for (int i = 0; i < len; 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);
}
}
}
for (int i = 1; i < len; i++) {
max = Math.max(max, dp[i]);
}
return max;
}
private static int maxLen(int[] arr) {
int len = arr.length;
int[] dp = new int[len+1];
dp[0] = 0;
int di = -1;
int dj = -1;
for (int i = 0; i < len; i++) {
di = i + 1;
dp[di] = 1;
for (int j = 0; j < i; j++) {
dj = j + 1;
if (arr[i] > arr[j]) {
dp[di] = Math.max(dp[di], dp[dj] + 1);
}
}
}
int max = 0;
for (int i = 1; i <= len; i++) {
max = Math.max(max, dp[i]);
}
return max;
}
}
发表于 2022-03-21 23:38:52
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int[n];
for(int i = 0;i < n;i++){
arr[i] = scan.nextInt();
}
int x = -1;
for (int i = 0; i < n; i++) {
int m = returnStep(arr, i);
if (m > x) {
x = m;
}
}
System.out.println(x);
}
public static int returnStep(int[] arr, int index) {
//{3,65,7,67,8,9,4,1,5,8,9} 1
int start = index;
int res = -1;
while (start < arr.length){
int count = 1;
int x = arr[index];
for (int i = start; i < arr.length; i++) {
if(arr[i] > x){
x = arr[i];
count ++;
}
}
start ++;
if(count > res){
res = count;
}
}
//System.out.println(res);
return res;
}
} 为什么我的只通过了 3/20,我想while循环来确定每一轮中最大的升序,main函数中的
for循环控制走多少轮,第一轮从index = 0开始,依次递增调用returnStep()返回概论中
的最大子升序
发表于 2022-03-14 17:23:39
回复(0)
// 这里的思路和24题合唱团一样
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int len = scan.nextInt();
int[] arrs = new int[len];
int[] rightNum = new int[len];
for(int i=0; i<len; ++i) {
arrs[i] = scan.nextInt();
rightNum[i] = 1;
}
for(int i=len-1; i>=0; --i) {
for(int j=len-1; j>i; --j) {
if((arrs[i] < arrs[j]) && (rightNum[i]< rightNum[j]+1)) {
rightNum[i] = rightNum[j] + 1;
}
}
}
// 从递增数组中获取最大值
int max = 0;
for(int val : rightNum) {
if(max < val) {
max = val;
}
}
System.out.println(max);
}
scan.close();
}
}
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int len = scan.nextInt();
int[] arrs = new int[len];
int[] rightNum = new int[len];
for(int i=0; i<len; ++i) {
arrs[i] = scan.nextInt();
rightNum[i] = 1;
}
for(int i=len-1; i>=0; --i) {
for(int j=len-1; j>i; --j) {
if((arrs[i] < arrs[j]) && (rightNum[i]< rightNum[j]+1)) {
rightNum[i] = rightNum[j] + 1;
}
}
}
// 从递增数组中获取最大值
int max = 0;
for(int val : rightNum) {
if(max < val) {
max = val;
}
}
System.out.println(max);
}
scan.close();
}
}
发表于 2022-02-23 11:06:53
回复(0)
其实就是最长上升子序列问题。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()){
int n=in.nextInt();
int[]arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
//最长上升子序列
int[]dp=new int[n];
dp[0]=1;
int max=1;
for(int i=1;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(arr[j]<arr[i]) dp[i]=Math.max(dp[i],dp[j]+1);
max=Math.max(dp[i],max);
}
}
System.out.println(max);
}
}
}
发表于 2022-01-11 17:02:51
回复(0)
问题信息
难度：
32条回答
2502收藏
41604浏览
通过挑战的用户
查看代码-
2023-02-23 10:30:44
-
2023-01-07 17:35:50 -
2022-10-15 10:45:27 -
2022-09-16 17:11:18 -
2022-09-16 17:05:54
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
