求数组中最长的邻接子序列

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

我推断，要打印子序列，我需要跟踪最长序列的开始和结束时间，然后让程序在这些elements上打印。但是我的代码似乎没有正确运行。没有给出错误，它只是运行，但不返回任何东西。

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

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