/**
* 数组A中存放很多数据,比如A={1,2,3,4,3,2,1,4,8,9,10};其中1,2,3,4/1,4,8,9,10都是递增子序列,1,4,8,9,10是最长的递增子序列。
*
* 寻找数组中的最长子序列,返回起始的索引值,如果没有递增子序列,那么返回-1
*
*
* @author fangtengfei
* @date 2010-5-16
*/
public class MaxIncreSeq {
public static void main(String[] args) {
int a[] = { 1, 2, 3, 4, 3, 2, 1, 4, 8, 9, 10 };
int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 2, 1, 4, 8, 9, 10, 11,
12, 13, 18, 19, 20, 21, 22, 1, 2, 3 };
findMaxInCreSeqIndex(a1);
}
private static int findMaxInCreSeqIndex(int[] a) {
// 最长序列长度
int MaxInCreSeqLength = 0;
int maxInCreSeqIndex = 0;
// 临时序列长度
int tempInCreSeqLength = 1;
int tempInCreSeqIndex = 0;
// 增长,则临时序列加一,不增长,则判断是否大于已存的最大序列,大则取代之
for (int i = 0; i < a.length - 1; i++) {
if (a[i + 1] > a[i]) {
tempInCreSeqLength++;
} else {
if (tempInCreSeqLength > MaxInCreSeqLength) {
MaxInCreSeqLength = tempInCreSeqLength;
maxInCreSeqIndex = tempInCreSeqIndex;
}
tempInCreSeqLength = 1;
tempInCreSeqIndex = i + 1;
}
// 如果序列一直增长到最后一个元素
if (i == a.length - 2) {
if (tempInCreSeqLength > MaxInCreSeqLength) {
MaxInCreSeqLength = tempInCreSeqLength;
maxInCreSeqIndex = tempInCreSeqIndex;
}
}
}
System.out.println(MaxInCreSeqLength);
System.out.println(maxInCreSeqIndex);
return -1;
}
}
分享到:
相关推荐
### 动态规划:最长单调递增子序列 在计算机科学和算法设计中,动态规划是一种重要的技术,用于解决优化问题。本篇文章将详细介绍如何利用动态规划求解一个经典问题——寻找给定序列中的最长单调递增子序列...
最长递增子序列(Longest Increasing Subsequence, LIS)问题是计算机科学中的一种经典动态规划问题,广泛应用于算法设计和分析。在给定的整数序列中,我们的目标是找到一个尽可能长的、不降序的子序列。这个子序列...
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
这篇实验报告主要探讨了在数据与算法领域中如何找到数列的最长递增子序列,这是一个常见的算法问题,尤其在计算机科学的算法设计与分析中占有重要地位。实验的目的是通过设计、实现和分析算法来锻炼解决问题的能力。...
算法导论,请给出一个O(n^2)时间的算法,使之能找出n个数的序列中最长的单调递增子序列
### 最长递增子序列的概念 在探讨最长递增子序列之前,我们首先明确几个基本概念。 #### 定义: 给定一个序列 \( L = \langle a_1, a_2, \ldots, a_n \rangle \),该序列由 \( n \) 个不同的实数组成。最长递增子...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中常见的算法问题,它在数组或序列中寻找一个尽可能长的严格递增子序列。这个问题在多种领域都有应用,比如股票交易策略、生物信息学等。在这个...
【最长的单调递增子序列】是动态规划领域的一个经典问题,主要目标是从一个给定的整数序列中找出一个尽可能长的递增子序列。在这个问题中,递增子序列指的是序列中的元素按照从小到大的顺序排列,但不一定是连续的。...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一种经典的动态规划问题,广泛应用于算法竞赛和实际编程场景。在这个Java实现中,我们将深入探讨如何找到一个序列中长度最长的递增子序列。 ...
本题“PTA丨最长连续递增子序列”是一个典型的动态规划问题,它涉及到数组处理、序列分析以及优化算法等方面的知识。 首先,我们要明确什么是“最长连续递增子序列”。在给定的整数数组中,一个连续递增子序列是指...
最长非递增子序列(Longest Non-Increasing Subsequence,简称LNIS)问题是一个经典的计算机科学问题,尤其在算法设计和分析领域具有重要意义。这个问题的目的是在给定的一个无序整数序列中找到一个子序列,这个子...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
在本实验中,我们将探讨如何使用Java编程语言解决“最长递增子序列”(Longest Increasing Subsequence, LIS)的问题。这是一个经典的动态规划问题,在计算机科学和算法设计中具有广泛的应用,例如在股票交易策略、...
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
在中科大软件学院开设的算法导论课程实验中,要求学生研究和实现最长递增子序列问题。最长递增子序列(Longest Increasing Subsequence,简称LIS)问题是一个经典的计算机科学问题,其目标是在一个无序的整数序列中...
最长递增子序列(Longest Increasing Subsequence, LCS)是计算机科学中一种经典的动态规划问题,常见于算法和数据结构的学习。在这个问题中,我们给定一个无序整数序列,目标是找到序列中的一个子序列,使得这个子...
最长递增子序列(Longest Increasing Subsequence, LIS)是计算机科学中一个经典的算法问题,主要涉及到了排序、数组处理和优化策略等概念。在这个场景中,我们将关注使用贪心算法和动态规划来解决这个问题,并结合...
在本实验中,我们关注的是“最长递增子序列”(Longest Increasing Subsequence, LIS)这一经典问题,它是算法课程中的一个核心课题,尤其在动态规划的应用上有着重要的地位。中科大软件学院的这个实验旨在让学生...
根据给定的文件信息,我们将深入探讨两个关键的IT领域知识点:动态规划在寻找最长单调递增子序列中的应用以及动态规划在图像压缩算法中的作用。 ### 一、动态规划与最长单调递增子序列 #### 知识点概述: **最长...
动态规划最长递增子序列 已经实现 请大家赐教