查找數組中最長的連續子序列

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; 

}