Iram Shahed - 7 months ago 29

Java Question

I am trying to the length of the longest sequence of numbers shared by two arrays. Given the following two arrays:

`int [] a = {1, 2, 3, 4, 6, 8,};`

int [] b = {2, 1, 2, 3, 5, 6,};

The result should be

`3`

`{1, 2, 3}`

The numbers must be in a sequence for the program to consider to count it.

I have thought about it and wrote a small beginning however, I am not sure how to approach this

`public static int longestSharedSequence(int[] arr, int[] arr2){`

int start = 0;

for(int i = 0; i < arr.length; i++){

for(int j = 0; j < arr2.length; j++){

int n = 0;

while(arr[i + n] == arr2[j + n]){

n++;

if(((i + n) >= arr.length) || ((j + n) >= arr2.length)){

break;

}

}

}

Answer

That is a very good start that you have. All you need to do is have some way of keeping track of the best `n`

value that you have encountered. So at the start of the method, declare `int maxN = 0`

. Then, after the `while`

loop within the two `for`

loops, check if `n`

(the current matching sequence length) is greater than `maxN`

(the longest matching sequence length encountered so far). If so, update `maxN`

to the value of `n`

.

Since you also want the matching elements to be in sequential order, you will need to check that the elements in the two arrays not only match, but that they are also 1 greater than the previous element in each array. Putting these together gives the following code:

```
public static int longestSharedSequence(int[] arr, int[] arr2) {
int maxN = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr2.length; j++) {
int n = 0;
// Check that elements match and that they are either the
// first element in the sequence that is currently being
// compared or that they are 1 greater than the previous
// element
while (arr[i + n] == arr2[j + n]
&& (n == 0 || arr[i + n] == arr[i + n - 1] + 1)) {
n++;
if (i + n >= arr.length || j + n >= arr2.length) {
break;
}
}
// If we found a longer sequence than the previous longest,
// update maxN
if (n > maxN) {
maxN = n;
}
}
}
return maxN;
}
```

Source (Stackoverflow)