Finding the count of common array sequencce

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 as the the longest common sequence between the two is{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;
                }
            }
        }

question is not clear. Should the length of both arrays be same in all the cases or different? — Rishabh Anand, Oct 27 '16 at 01:19
So it looks like you are trying to store the final value in `n`? What is the current result of running your program? — mapeters, Oct 27 '16 at 01:23
n is just a variable that adds to check if the values are equal. At the moment I am not sure what to return. — Iram Shahed, Oct 27 '16 at 01:30
Possible duplicate of [How do I get the intersection between two arrays as a new array?](http://stackoverflow.com/questions/13270491/how-do-i-get-the-intersection-between-two-arrays-as-a-new-array) — Tibrogargan, Oct 27 '16 at 01:34
So if you had these inputs - int [] a = {1, 2, 3, 4, 6, 8,}; int [] b = {1, 2, 2, 3, 5, 6,}; would that mean the result is 2? — D.B., Oct 27 '16 at 01:35

mapeters · Accepted Answer · 2016-10-27T02:16:40.393

1

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;
}

edited Oct 27 '16 at 02:16

answered Oct 27 '16 at 01:32

mapeters

1,067
7
11

What should I return? – Iram Shahed Oct 27 '16 at 01:41
@IramShahed `maxN`. The way you currently have it, `n` is the matching sequence length starting from `i` and `j` in the two arrays, so you just need to have a way of keeping track of the largest `n` value that you encounter, which is what `maxN` is for. – mapeters Oct 27 '16 at 01:42
` 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; while(arr[i + n] == arr2[j + n]){ n++; if(((i + n) >= arr.length) || ((j + n) >= arr2.length)) break; } if(n > maxN){ maxN = n; } } } return maxN; } – Iram Shahed Oct 27 '16 at 01:50
Sorry I am having trouble formatting it. However I tested it it worked for the two arrays I wrote in the actual question however It didn't work when I changed the 5 to a 4 in array b, it returned 5. – Iram Shahed Oct 27 '16 at 01:52
@IramShahed so the numbers need to be sequential also? Like if both arrays have `{1, 3, 7}` in them, the method shouldn't return 3? – mapeters Oct 27 '16 at 01:53
Yes, I didn't mention that but its looking for a sequence that common not just the elements. – Iram Shahed Oct 27 '16 at 01:55
@IramShahed I have updated my answer, including code that should work for this. Let me know if you still run into issues. – mapeters Oct 27 '16 at 02:17
Thank you I got it to work on my laptop. I am getting a failed message when I test with my teachers array so I will need to debug a little bit, – Iram Shahed Oct 27 '16 at 02:30

score -1 · Answer 2 · answered Oct 27 '16 at 01:50

-1

I didn't think of anything smarter than the path you were already on:

import java.util.Arrays;
import java.util.Random;

public class MaxSeq {
  public static void main(String... args) {
    int[] a = new int[10000];
    int[] b = new int[10000];
    final Random r = new Random();
    Arrays.parallelSetAll(a, i -> r.nextInt(100));
    Arrays.parallelSetAll(b, i -> r.nextInt(100));
    System.out.println(longestSharedSequence(a, b));
  }

  private static int longestSharedSequence(final int[] arr, final int[] arr2) {
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
      for (int j = 0; j < arr2.length; j++) {
        int n = 0;
        while ((i + n) < arr.length
            && (j + n) < arr2.length
            && arr[i + n] == arr2[j + n]) {
          n++;
        }
        max = Math.max(max, n);
      }
    }
    return max;
  }
}

see: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

answered Oct 27 '16 at 01:50

Andreas

4,937
2
25
35

What exactly is the function of `max = Math.max(max, n);`? – Iram Shahed Oct 27 '16 at 01:57
[Max](https://docs.oracle.com/javase/7/docs/api/java/lang/Math.html#max(long,%20long)) returns the greater of two long values. That is, the result is the argument closer to the value of Long.MAX_VALUE. If the arguments have the same value, the result is that same value. – Andreas Oct 27 '16 at 01:59
Doesn't work for inputs: a = new int[]{1, 3, 5, 4, 6, 8}; b = new int[]{2, 1, 2, 3, 5, 6}; The question says "The numbers must be in a sequence for the program to consider to count it." – D.B. Oct 27 '16 at 02:24
@D.B. {1, 3, 5, 4, 6, 8} and {2, 1, 2, 3, 5, 6} yields longest sequence length of two. Looks right to me: {3, 5} being the longest. What output were you expecting? – Andreas Oct 27 '16 at 04:10
@Andreas I interpret "numbers must be in a sequence" to mean that each number in the subset must be 1 greater than the previous. E.g. 1,2,3 is a sequence but 3,5 is not because 3+1 != 5 – D.B. Oct 27 '16 at 04:14
@D.B. I saw that and deleted my comment. I see that it does. – Andreas Oct 27 '16 at 17:53

Finding the count of common array sequencce

2 Answers2