查找数组中最长的连续子序列
我的任务是编写一个程序，找到给定数组中增长最长的连续子序列，并打印该子序列的长度和它自己的子序列。 说数组是：
int[] arr = {3, 6, 5, 1, 9, 3, 2, 3, 4, 5, 1} 最长的连续增加子序列是2,3,4,5，长度为4.因此这种方法的输出将是
4 2, 3, 4, 5
到目前为止这是我的代码：
public class LongestSubsequence { public static void main(String[] args) { // Test arrays int[] arrC = {9, 5, 2, 3, 4, 5}; int[] arrA = {1, 2, 3, 4, 5, 7}; int[] arrB = {7, 6, 5, 4, 1, 2}; int[] arr = {3, 6, 5, 1, 9, 3, 2, 3, 4, 5, 1}; longestForward(arr); } // input of the int array, returns nothing. public static void longestForward(int[] arr) { // variables for Length of longest subsequence found and for the length of the current sequence int subSeqLength = 1; int longest = 1; boolean longestSub = false; int indexStart = 0; int indexEnd = 0; for (int i = 0; i < arr.length-1; i++) { //Increases subsequence length variable if (arr[i] longest) { longest = subSeqLength; longestSub = true; } // if the current sequence being analyzed is the longest one, keeps track of where it starts and ends else if (longestSub = true) { arr[i] = indexStart; arr[i+1] = indexEnd; } // sets the subsequence length back to one if it is no longer increasing else subSeqLength = 1; } System.out.println(subSeqLength); System.out.println(indexStart); System.out.print(indexEnd); } }
所以我想出了如何让程序识别最长子序列的长度。 但是，我仍然坚持如何实际打印它。 现在，我只是试图让方法正确地打印最长子序列开始和结束的数组中的位置。 这不是程序中需要的东西，但我认为在进行打印之前我需要弄清楚这一点。
我推断要打印子序列，我需要跟踪最长序列何时开始和结束，并从那里得到程序在这些元素上打印。 但我的代码似乎没有正确运行。 没有给出错误，只是运行但不返回任何内容。
任何帮助是极大的赞赏。 谢谢！
在这里，我用注释修复了你的算法：
public static void longestForward(int[] arr) { int subSeqLength = 1; int longest = 1; int indexStart = 0; int indexEnd = 0; for (int i = 0; i < arr.length - 1; i++) { if (arr[i] == arr[i + 1] - 1)//We need to check if the current is equal to the next { subSeqLength++;//if it is we increment if (subSeqLength > longest)//we assign the longest and new bounds { longest = subSeqLength; indexStart = i + 2 - subSeqLength;//make sure the index start is correct indexEnd = i + 2; } } else subSeqLength = 1;//else re-initiate the straight length } for (int i = indexStart; i < indexEnd; i++)//print the sequence System.out.println(arr[i] + ", "); }
arr[i] = indexStart; arr[i+1] = indexEnd;
你想让它走另一条路，赋值运算符从右到左分配值，但你可能已经知道了。 但这不是最大的问题，你的代码是错误的，不能给你正确的答案，并且有一些问题。
首先，前面提到的indexStart和indexEnd。 您希望存储数组的索引，但实际上您尝试将值存储在这些单元格中。
此外，每次子序列长度增加时，都应该跟踪子序列的结束。 你if/else if逻辑是错误的，你必须改进它。 当你在它上面时， isLongest在真实之后永远不会是假的，这很糟糕。 你需要检查这是否是最长的子序列，只有当它结束时，所以当你第一次if是假的时候。
for (int i = 0; i < arr.length-1; i++) { if (arr[i] < arr[i+1]) { subSeqLength++; } else { if ( subSeqLength > longest ) { indexStart = i - subSeqLength + 1; longest = subSeqLength; } subSeqLength = 1; } } System.out.println(longest); System.out.println(indexStart); System.out.println(indexStart + longest-1);
这是我在JS中的答案
function longestContigousSubsequence(seq) { // to pointers to point at the current and next var count; var j; var i = 0; var result = 0; var temp = []; var final = [] // if array length is 1, return the empty array while(i < seq.length - 1){ count = 0; j = i + 1; temp.push(seq[i]) while(seq[i] < seq[j] && j < seq.length){ count += 1; temp.push(seq[j]) j += 1 i += 1 } if(count > result){ result = count; final = temp; } i += 1; temp = []; //console.log(i + " " + count); } return final; }