Максимальная арифметическая последовательность двух разных массивов

Question

Учитывая два массива целых чисел, a и b, попробуйте создать арифметическую последовательность, добавив целые числа из b в a. Вернуть максимальную длину a или -1, если не существует арифметической последовательности, например, a = [2, 4, 8], b = [1, 6, 10, 12] -> a = [2, 4, 6,8, 10, 12] -> return 6

Я пытался создать новый массив и объединить a и b и подсчитать самую длинную подпоследовательность, но счетчик мог удалить элементы из a, к которым не следует прикасаться

static int maxSeq(int[] arr1, int[] arr2){
        if(arr1.length ==0)return 0;
        int n =arr1.length, m = arr2.length;
        int[] arr = new int[n+m];
        System.arraycopy(arr1,0,arr,0,n);
        System.arraycopy(arr2,0,arr,n,m);
        Arrays.sort(arr);
        int result =0;
        Map<Integer,Integer>[]d = new HashMap[n+m];
        for(int i =0; i < arr.length;i++){
            d[i] = new HashMap<Integer, Integer>();
        }
        for(int i =1; i < arr.length; ++i){
            for(int j = 0; j<i;++j ){
                int diff = arr[i]-arr[j];

                int len =2;

                if(d[j].containsKey(diff)){
                    len = d[j].get(diff) +1;
                }



                d[i].put(diff,len);

                result = Math.max(result,d[i].get(diff));


            }
        }
        return result;
    }

a = [2, 4, 8], b = [1, 6, 10, 12] -> a = [2, 4, 6, 8, 10, 12] -> return 6 int []a = {5,7,13,14}, b = {9,11,15};возврат -1 не 6

Answer 1

Я думаю, вы должны попытаться исправить свой код.

if(d[j].containsKey(diff)){ len = d[j].get(diff) +1; }

Здесь вы ищете differences в карте с некоторым индексом j, и должен быть только одинкарта пар значений ключей, а не массив карт.

Answer 2

Вероятно, проще всего использовать список и подсписок.

   public static void main(String[] args) {

      // generate some test data for verification.  The list with the * is
      // the actual sequence which can be commented out if not wanted.
      Random r = new Random();
      int[][] testCases = IntStream.range(0, 20).mapToObj(
            a -> r.ints(r.nextInt(6) + 3, 0, 30).toArray()).toArray(
                  int[][]::new);


      for (int i = 0; i < testCases.length - 1; i++) {
         int[] a = testCases[i];
         int[] b = testCases[i + 1];
         System.out.println(Arrays.toString(a));
         System.out.println(Arrays.toString(b));
         System.out.println(maxseq(a, b));
         System.out.println("---------------------------");
      }
      // System.out.println(maxSeq(a, b));
   }
   }

   public static int maxseq(int[] a, int[] b) {

     // copy arrays to main list
      List<Integer> ab = new ArrayList<>();
      for (int i : a) {
         ab.add(i);
      }
      for (int i : b) {
         ab.add(i);
      }

      // sort list in ascending order
      Collections.sort(ab);

      // empty sublist
      List<Integer> subList = List.of();

      int start = 0;
      for (int i = 2; i < ab.size(); i++) {
         // get initial difference
         int d = ab.get(start + 1) - ab.get(start);
         if (ab.get(i) - ab.get(i - 1) == d) {
            // update sublist if difference is same
            subList = ab.subList(start, i + 1);
         }
         else {
            // else start anew.
            start = i - 1;
         }
      }
      // and return result
      System.out.println("*" + subList());
      return subList.size() > 2 ? subList.size()
            : -1;
   }