在一个数组中找到最长的连续子序列

Question

在一个数组中找到最长的连续子序列

7

我的任务是编写一个程序，找到给定数组中最长的递增连续子序列，并打印出该子序列的长度和内容。例如，如果数组为：

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

所以我已经找出了如何使程序识别最长子序列的长度。然而，我卡在了如何实际打印它上面。现在，我只是尝试让方法正确地打印最长子序列开始和结束的数组位置。这不是程序所需要的，但我认为在继续打印之前需要弄清楚这一点。

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

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

- Zephyr

为什么不创建一个函数来返回最长的连续子序列（如果存在多个最大长度的连续子序列，则返回第一个）？然后，您只需执行 subSequence.length（或其他操作）即可获取其长度。 - user554546

只是另一种实现相同事物的方式。看看这个链接是否能给你一些提示：http://www.sanfoundry.com/java-program-implement-longest-arithmetic-progression-algorithm/ - Chetan Kinger

我不确定你所说的“创建一个函数”是什么意思。你是指创建一个帮助方法，返回正确的数组并将其传递给我的longestForward方法，然后再将其传递给我的主方法吗？如果是这样，我该怎么做呢？我已经尝试了很多次这段代码的迭代来跟踪我想要的结果，但我就是想不出来。能给我一些起点吗？ - Zephyr

为什么你需要将 longestForward 设为 void 类型？为什么不直接在 main 函数中打印呢？ - user554546

这个任务非常具体：实现一个名为longestForward的方法，该方法以int数组作为输入，并返回无输出。此方法打印两行文本。第一行是一个数字，即LICS的长度。第二行是子序列本身的实际元素，用逗号分隔。如果有相同长度的多个LICS，请打印第一个。 - Zephyr

显示剩余3条评论

3个回答

1

arr[i] = indexStart;
arr[i+1] = indexEnd;

你希望它反过来，赋值运算符从右到左赋值，但你可能已经知道了。但这不是最大的问题，你的代码是错误的，无法给出正确的答案，而且存在一些问题。

首先，上述的indexStart和indexEnd。你想要存储数组的索引，但实际上你尝试在这些单元格中存储值。

此外，在子序列长度增加时，跟踪子序列的结束应该每次都进行。你的if/else if逻辑是错误的，你必须改进它。当你第一次的if为false时，isLongest永远不会变为false，这很糟糕。你需要在子序列结束时才检查是否是最长的子序列，因此当你的第一个if为false时。

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

- zubergu

啊，发现得好。代码现在可以运行了。不幸的是，它没有返回任何正确的值。当我注释掉索引else if循环时，它会返回正确的长度值（但不是正确的indexStart和End值）。仍然卡住了。 - Zephyr

在Jean-Francois的回答之后，我比较了他的else if逻辑和我的。我想我发现了我的错误。我在布尔值上出了问题，我的代码不规律地跟踪了结尾，并没有在每次迭代中递增它。感谢您的有益评论。 - Zephyr

0

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

}

- dag332

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jean-François Savard · Accepted Answer

我用注释修复了你的算法：

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