Finding the longest increasing contiguous subsequence

Question

I'm attempting to write a program that takes a sequence as an array, then prints the longest contiguous subsequence, as well as its length. In the code I've written thus far (below), I've managed to accomplish this in the method longestForward. However, in the assignment specification I've also been asked to write another method, longestBackwards, that accomplishes the exact same task ie. will print the exact same thing, but it must search the original array backward. This is where I'm having difficulty.

I've managed to write a method that prints only the last two members of the longest contiguous subsequence, and in reverse order (for example, for the array 4, 5, 6 it prints 6, 5). However it does print the length correctly.

If anyone can help figure out what I've done wrong that would be much appreciated.

import java.util.Scanner;
public class LongestSubsequence {
public static void main(String[] args) {

    // Test array
    int[] arr = {4, 5, 6};


    longestForward(arr);
    longestBackward(arr);

  }

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] )//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;
                indexEnd = i + 2;
            }

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

System.out.println(longest);
    for (int i = indexStart; i < indexEnd; i++)//print the sequence

      System.out.print(arr[i] + ", ");  
}
public static void longestBackward(int[] arr) {

    int subSeqLength = 1;
    int longest = 1;
    int indexStart = 0;
    int indexEnd = 0;
    for (int i = arr.length - 1; i > 0; i--) {
        if (arr[i] > arr[i - 1]) { 
            subSeqLength++;
            if (subSeqLength > longest) {
                longest = subSeqLength;
                indexStart = i + (subSeqLength - 1); 
                indexEnd = i - 1;
            }
        } // Else re-initiate the length
        else {
            subSeqLength = 1;
        }
    }
System.out.println("");
    // Print the sequence
System.out.println(longest);
    for (int i = indexStart-1; i > indexEnd; i--) {
        System.out.print(arr[i] + ", ");
    }
}
}

Just hold the array up to a mirror. (And just to confound things: It is possible, on average, to do a bit better than O(N), though probably not as well as O(log N).) — Hot Licks, Feb 24 '15 at 19:58

score 0 · Answer 1 · answered Feb 24 '15 at 19:40

0

Just to clarify.. Why can't you take the longest forward and reverse it? Wouldn't the longest forward be the reverse of the longest backward?

answered Feb 24 '15 at 19:40

Kira Faye

31
4

Oh, I think that is actually allowed, as long as I create a new array that simply reverses the elements. How would I go about this? – Feb 24 '15 at 19:45
Wait, I'm confused now. Do I simply reverse the array found at the end (which is still missing a number) or do I have a really simple longestBackwards now? Keep in mind longestBackwards needs to print the same array as longestForwards. – Feb 24 '15 at 19:57

score 0 · Answer 2 · answered Feb 24 '15 at 20:10

for (int i = arr.length - 1; i > 0; i--) {
    if (arr[i] > arr[i - 1]) { 
        subSeqLength++;
        if (subSeqLength > longest) {
            longest = subSeqLength;
            indexStart = i + (subSeqLength - 1); 
            indexEnd = i - 1;
        }
    } // Else re-initiate the length

Shouldn't the for loop look a bit more like this:

for (int i = arr.length - 1; i >= 0; i--) {

You're not getting arr[0] because you're stopping after arr[1].

Finding the longest increasing contiguous subsequence

2 Answers2