CODEWITHSUNDEEP
javaarrays
Miranda Green
Miranda Green

Reputation: 1

Find increasing contiguous subsequence with two loops

I'm trying to find the longest contiguous subsequence within an input array. My current code has an outer loop that starts a sequence from each index of the input, and an inner loop that iterates through all the elements following the starting index. I know this can be solved by simply setting a start and end index, and copying a range of the array, but I can't figure out why this code doesn't recognize a decrease from one element to another. When I run the program, it still prints the entire input array.

import java.util.Arrays;

public class LongestSubsequence {

 public static void longestForward(int[] input) {
   int length = 1; 
   int longest = 1;
   int[] currentSubsequence = new int[input.length];
   int[] longestSubsequence = new int[input.length];

   //Two loops: outer loop iterates through elements of the array 
   //and makes each one the starting index before executing inner loop
   for (int i = 0; i < input.length-1; i++) {
     currentSubsequence[i] = input[i];

     //next loop iterates through all proceeding elements in the array 
     //after the starting index
     for (int j = i + 1; j < input.length; j++) { 
       //if the next element is greater than the previous element in the 
       // subsequence array, it is appended to the array
       if(input[j] > currentSubsequence[j-1]) {
         currentSubsequence[j] = input[j];
         length++;
       }
       //otherwise the length of the subsequence is compared to the 
       //longest so far, if it is bigger it sets the longest subsequence
       //to the current subsequence
       else if(input[j] < currentSubsequence[j-1]) {
         if(length > longest) {
           longest =length;
           longestSubsequence = currentSubsequence;
         }
       }
     }
   }
   int[] finalArray = Arrays.copyOfRange(longestSubsequence, 0, length);
   System.out.println(Arrays.toString(finalArray));
 }

  public static void main (String[] args) {
    int[] x = {1, 2, 3, 2, 6};
    longestForward(x);
  }
}

Upvotes: 0

Views: 203

Answers (1)

J. Nuutinen
J. Nuutinen

Reputation: 11

You forgot to reset your current length variable:

else if(input[j] < currentSubsequence[j-1]){
    if(length > longest){
        longest =length;
        longestSubsequence = currentSubsequence;
    }
    length = 1; // Add this
}

EDIT:

I just realized this won't fix the whole problem, I think you'll need to get the starting index of the longest sequence and use that in the copyof.

Upvotes: 1

Related Questions