查找数组中最长的连续子序列

Question

我的任务是编写一个程序，该程序在给定的数组中找到最长的连续子序列，并打印该子序列的长度以及它自身的子序列。 说阵列是：

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] < arr[i+1]) { 
     subSeqLength++; 
     } 
     // Sets the current subsequence to the longest variable if it is the longest one found at the time. 
     else if (subSeqLength > 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); 
    } 
} 

所以我想通了如何让程序识别最长的子序列的长度。但是，我坚持要如何才能真正将它打印出来。现在，我只是试图让方法正确地打印出阵列中最长的子序列开始和结束的地方。这不是程序中需要的，但我认为在开始打印之前我需要弄清楚这一点。

我推断，为了打印子序列，我需要跟踪最长序列何时开始和结束，并从那里获得打印在这些元素上的程序。但我的代码似乎没有正确运行。没有给出的错误，它只是运行，但不返回任何东西。

任何帮助，非常感谢。谢谢！

Answer 1

在这里，我固定评论你的算法：

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] + ", ");   
} 

Answer 2

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); 

Answer 3

这是我在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; 

}