CODEWITHSUNDEEP
javaarrays
Zephyr
Zephyr

Reputation: 95

Searching an Array backwards for longest contiguous subsequence

This is a follow-up question to my previous question.

I'm looking to find the longest contiguous sequence in an array that is searched backwards.

Thank you for any and all help.

This is my current method:

 public static void longestBackward(int[] arr)
  {

    int subSeqLength = 1;
    int longest = 1;
    boolean longestSub = false;
    int indexStart = 0;
    int indexEnd = 0;

    for (int i = arr.length-1; i > 0; i--)
    { // We need to check if the current is equal to the previous
        if (arr[i] < arr[i-1])
        {   // if it is we increment the length
            subSeqLength++;
            // Assign the longest to the current subsequence if it's the longest
            if (subSeqLength > longest)
            {
                longest = subSeqLength;
                longestSub = true;
            }
            // We set the new index end if it is the longuest

            if (longestSub)
            {
                indexStart = i + 2 - subSeqLength;
                indexEnd = i + 2;
            }

        }
        // Else re-initiate the length
        else
            subSeqLength = 1;
    }

    System.out.println(longest);

    // Print the sequence
    for (int i = indexEnd; i < indexStart; i--)
        System.out.print(arr[i] + ", ");        
  }

Upvotes: 2

Views: 128

Answers (2)

Jean-Fran&#231;ois Savard
Jean-Fran&#231;ois Savard

Reputation: 21004

I fixed your code and commented in it what I changed :

public static void longestBackward(int[] arr) {

    int subSeqLength = 1;
    int longest = 1;
    int indexStart = 0;
    int indexEnd = 0;

    /**
     * We iterate while we are higher then 0 not 1 as we retrieve i - 1
     */
    for (int i = arr.length - 1; i > 0; i--) {
        if (arr[i] > arr[i - 1]) {//I've changed < to > remember we are backward. 
            subSeqLength++;

            /*
             * I've removed the longestSub which is useless
            */
            if (subSeqLength > longest) {
                longest = subSeqLength;
                indexStart = i + (subSeqLength - 1); //notice that I modified the bounds
                indexEnd = i - 1;
            }
        } // Else re-initiate the length
        else {
            subSeqLength = 1;
        }
    }

    // Print the sequence
    for (int i = indexStart - 1; i > indexEnd; i--) {
        System.out.print(arr[i] + ", ");
    }
}

Make sure you comment if there is some part of it you don't understand.

Upvotes: 1

mk.
mk.

Reputation: 11710

for (int i = arr.length-1; i >= 0; i--)
    {
        if (arr[i-1] < arr[i - 2])

In the first line, i can be 0. In the Third, i-1 would be -1, which is out of bounds for an array. You might want to write i>1, or similar.

Have you tried simply reversing the array, and then feeding the reversed array into your original, working method?

Upvotes: 1

Related Questions