瞿肖

用户名：uq_33500452490

访问量：1676

签　名：

等　　级
排　　名	4520
经　　验	1679
参赛次数	1
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

全天下的温柔共十分，你占八分，遇见你那晚的凉风秋月占一分，你说你也喜欢我的那刻占一分。

TA的其他文章

同样的道理维护最大上升子序列
浏览：101

遍历所有元素的最长上升、下降子序列，取最长的
浏览：59

保存第一个，取的值，单独算最后一个
浏览：53

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

遍历所有元素的最长上升、下降子序列，取最长的

　　作者: 瞿肖　　　　发表时间：2023-03-20 10:13:49 浏览：59　|　评论：0　

原题链接：怪盗基德的滑翔翼

题目已经说了，任一点起飞，我们就得把全部点都遍历一次，所以外面套上循环，0-n
把所有节点的最长上升、下降加入集合，最后排序取最大的，你也可以用一个变量一直维持最大的，我嫌麻烦没怎么做。

import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		for (int index = 0; index < k; index++) {
			ArrayList<Integer> list = new ArrayList<Integer>();
			int n = sc.nextInt();
			int[] arr = new int[n];
			int[] dp1 = new int[n];
			int[] dp2 = new int[n];
			int max = -1;
			for (int j = 0; j < n; j++) {
				arr[j] = sc.nextInt();
				dp1[j] = 1;
				dp2[j] = 1;
			}
			int max1 = -1;
			int max2 = -1;
			for (int i1 = 0; i1 < n; i1++) {
				// 往右边找最大上升
				max1 = -1;
				for (int i = i1; i < n; i++) {
					for (int r = 0; r < i; r++) {
						if (arr[i] < arr[r]) {
							dp1[i] = Math.max(dp1[i], dp1[r] + 1);
						}
						max1 = Math.max(max1, dp1[i]);
					}
				}
				list.add(max1);
	//				System.out.println(Arrays.toString(dp1)+":"+max1);
	//				System.out.println("***********************");
				// 往左边找最长下降
				max2 = 1;
				for (int i2 = 0; i2 <= i1; i2++) {
					for (int j = 0; j < i2; j++) {
						if (arr[i2] > arr[j]) {
							dp2[i2] = Math.max(dp2[i2], dp2[j] + 1);
						}
						max2 = Math.max(dp2[i2], max2);
					}
				}
				list.add(max2);
	//				System.out.println(Arrays.toString(dp2)+":"+max2);
			}
			Collections.sort(list);
			System.out.println(list.get(list.size() - 1));
		}
	}
	}

啦啦啦————故得白！

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

瞿肖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

转化为字符数组

1065

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

遍历所有元素的最长上升、下降子序列，取最长的

评论区

精彩推荐

Tom数（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

大神老白（C语言代码）

【偶数求和】（C语言代码）

【偶数求和】（C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1017题解

Quadratic Equation （C语言代码）

瞿肖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

转化为字符数组

1065

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

遍历所有元素的最长上升、下降子序列，取最长的

评论区

精彩推荐

Tom数 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

大神老白 （C语言代码）

【偶数求和】 （C语言代码）

【偶数求和】 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1017题解

Quadratic Equation （C语言代码）

　　评论区

Tom数（C语言代码）

大神老白（C语言代码）

【偶数求和】（C语言代码）

【偶数求和】（C语言代码）