Finding the longest contiguous subsequence in an array

Question

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}

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

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.

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.

Any help is greatly appreciated. Thanks!

Answer 1

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

Answer 2

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

You want it to go the other way, assignment operator assigns value from right to left, but you probably know that already. But it's not the biggest problem, your code is wrong and can't give you correct answer and there are a few problems.

First of all, forementioned indexStart and indexEnd. You want to store indexes of your array but you actually try to store values in those cells.

Also, keeping track of end of you subsequence should be done every time your subsequence length increases. You if/else if logic is wrong and you have to improve it. While you're on it, isLongest is never false after being true once, that's bad. You need to check if this is the longest subsequence only when it ends, so when you first if is 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);