I have a code that is supposed to take two sequences X and Y, and find the longest common subsequence S (**but the elements must be consecutive (one after the other) in both X and Y)

The problem is that when I ran my code with this example:

X = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

Y = { 13, 15, 18, 1, 3, 5, 8, 10, 12, 20}

it gave me the out put:

S = { 8, 10, 12, 20} Which is wrong because 20 is not consecutive with the other elements in BOTH X and Y.

The answer is supposed to be:

S = { 8, 10, 12} with the length 3

I was told to save the previous value to compare it with the current value but when I did that it gave me an "index out of bound exception.

Here's my original code:

import java.util.Scanner;

public class LCS {

public static void main(String[] args) {

System.out.println();

Scanner input = new Scanner(System.in);

// Taking the elemest and length of X and Y from user

System.out.print("Enter the length of the sequences X and Y: ");

int n = input.nextInt();

int[] X = new int[n];

int[] Y = new int[n];

System.out.print(" Enter the elements of sequence X: ");

for (int i = 0; i < n; i++) {

X[i] = input.nextInt();

}

System.out.print(" Enter the elements of sequence Y: ");

for (int i = 0; i < n; i++) {

Y[i] = input.nextInt();

}

input.close();

// Printing X and Y

System.out.println();

System.out.print("X = {");

for (int i = 0; i < n; i++) {

System.out.print(X[i]);

if (i != n - 1) {

System.out.print(", ");

}

}

System.out.print("}");

System.out.println();

System.out.print("Y = {");

for (int j = 0; j < n; j++) {

System.out.print(Y[j]);

if (j != n - 1) {

System.out.print(", ");

}

}

System.out.print("}");

// Finding the LCS

int[][] lcs = new int[n + 1][n + 1];

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (X[i - 1] == Y[j - 1]) {

lcs[i][j] = lcs[i - 1][j - 1] + 1;

} else {

lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);

}

}

}

// Getting the length of LCS

int length = lcs[n][n];

// Getting the LCS elements

int[] S = new int[length];

int i = n;

int j = n;

int k = length - 1;

while (i > 0 && j > 0) {

if (X[i - 1] == Y[j - 1]) {

S[k--] = X[i - 1];

i--;

j--;

} else if (lcs[i - 1][j] > lcs[i][j - 1]) {

i--;

} else {

j--;

}

}

// Printing the LCS elements

System.out.println(" ");

System.out.print("Longest common subsequence is S = {");

for (int m = 0; m < length; m++) {

System.out.print(S[m]);

if (m != length - 1) {

System.out.print(", ");

}

}

System.out.print("}");

// Printing the length of LCS

System.out.print("with length " + length);

System.out.println(" n = " + length);

// Finding the starting index in X and Y

int startIndexX = -1;

int startIndexY = -1;

for (i = 0; i < n; i++) {

if (X[i] == S[0]) {

startIndexX = i;

break;

}

}

for (j = 0; j < n; j++) {

if (Y[j] == S[0]) {

startIndexY = j;

break;

}

}

// Printing the start index of X and Y

System.out.println("i = " + startIndexX);

System.out.println("j = " + startIndexY);

System.out.println();

}

}

Here's the update on it to save the previous value: (in the while loop)

int[] S = new int[length];

int i = n;

int j = n;

int k = length - 1;

int prev = -1;

while (i > 0 && j > 0) {

if (X[i - 1] == Y[j - 1] && prev + 1 == X[i - 1]) {

S[k--] = X[i - 1];

i--;

j--;

prev = X[i - 1];

} else if (lcs[i - 1][j] > lcs[i][j - 1]) {

i--;

} else {

j--;

}

if (X[i - 1] == Y[j - 1] && prev + 1 != X[i - 1]{

prev = -1;

}

}

How do I fix this issue?