寻找最长连续子序列中的阵列 [英] Finding the longest contiguous subsequence in an array

问题描述

我的任务是写一个查找给定的数组，并打印了两个序列的长度最长的连续增加一个子程序，并且序列它的自我。
说数组是：

My assignment is to write a program that finds the longest increasing contiguous subsequence in a given array and prints both the length of that subsequence, and the subsequence it self. Say the array is:

int[] arr = {3, 6, 5, 1, 9, 3, 2, 3, 4, 5, 1}

最长连续递增子是2，3，4，5为4的长度。
所以该方法的输出将是

The longest continuous increasing subsequence is 2, 3, 4, 5 with a length of 4. So the output of this method would be

4
2, 3, 4, 5

这是我的code迄今：

This is my code so far:

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

所以，我已经想通了如何让程序可以识别最长序列的长度。但是，我坚持我如何能真正得到它打印。现在，我只是试图让该方法正确打印的地方数组，其中最长的子开始和结束英寸这是不是需要在程序中，但我想我需要才去到打印出来摸不着头脑。

So I've figured out how to get the program to identify the length of the longest subsequence. However, I'm stuck on how I can actually get it to print. Right now, I'm just trying to get the method to correctly print the place in the array where the longest subsequence starts and ends. This is not what needs to be in the program, but I thought I would need to figure this out before going on to printing it.

我的理由是，打印序列，我需要保持在最长序列开始和结束的轨道，并从那里得到的程序来打印这些elemennts。但我的code似乎没有被正确运行。有没有给出错误，它只是运行，但不返回任何东西。

I reasoned that to print the subsequence, I would need to keep track of when the longest sequence started and ended, and from there get the program to print on those elemennts. But my code doesn't seem to be running correctly. There are no errors given, it just runs but doesn't return anything.

任何帮助是极大AP preciated。谢谢！

Any help is greatly appreciated. Thanks!

推荐答案

下面我固定的算法评论：

Here I fixed your algorithm with comments :

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

这篇关于寻找最长连续子序列中的阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！