Мой код разделительной последовательности не решает все проблемы, представленные ему

Question

Эта проблема касается последовательностей натуральных чисел a1, a2,…, aN.Подпоследовательность последовательности - это все, что получается путем отбрасывания некоторых элементов.Например, 3,7,11,3 - это подпоследовательность 6, 3 , 11,5, 7 , 4,3, 11 , 5, 3 , но 3,3,7 не является подпоследовательностью 6,3,11,5,7,4,3,11,5,3.

Полностью разделяющая последовательностьпоследовательность a1, a2,…, aN, где ai делит aj всякий раз, когда i

Учитывая последовательность целых чисел, ваша цель состоит в том, чтобы найти длину самой длинной полностью делительной подпоследовательности этой последовательности.

Рассмотримпоследовательность 2,3,7,8,14,39,145,76,320

Она имеет полностью делительную последовательность длины 3, а именно 2,8 320, но ни одной длины 4 или больше.

Рассмотримпоследовательность 2,11,16,12,36,60,71,17,29,144,288,129,432,993.

Имеет две полностью разделяемые подпоследовательности длины 5 - (2,12,36,144,288) или (2,12,36,144,432).

Чтобы решить эту проблему, я написал следующий код:

import java.util.Scanner;

class DivSeq {

  private int n, input[];

  void accept() {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    input = new int[n];
    for(int i = 0; i<n; i++)
    input[i] = sc.nextInt();
    sc.close();         
}

int size(int a[]) {
    //this function returns the number of non zero entries in an array
    int ctr = 0;
    for(int i = 0; i<a.length; i++) {
        if(a[i]==0)
        break;
        else
        ctr++;
    }
    return ctr;
  }

  int sequence() {
    int subseq[], pvrseq[], seq[], j, a = 1, q, k = 1, f = 0;
    subseq = new int [n]; 
    pvrseq = new int [n];
    seq = new int [n]; 
    for(int i = 0; i<n-1; i++) {
        k = 1;
        for(int c = 0; c<seq.length; c++)
        seq[c] = 0;
        //seq has been initialized, now inserting 1st value
        seq[0] = input[i];
        //creating the sequence
        for(j = i+1; j<n; j++) {
            if(input[j]%input[i]==0) 
            seq[k++] = input[j];
        }
        //if size of sequence is 1, then there is no use of checking it
        if(size(seq)<2)
        continue;
        subseq[0] = seq[0];
        a = 1;
        while(a<size(seq)-1) {
            k = 2;
            for(int p = a; p<size(seq)-1; p++) {
                //initial value of subsequence
                if(subseq[1] == 0)
                subseq[1] = seq[p];
                //creating the subsequence
                for(q = p+1; q<size(seq); q++) {  

                    if(seq[q]%seq[p]==0) {
                        subseq[k++] = seq[q];
                        p = q-1;
                        f = 1;
                        break;
                    }

                }
                if(f==1 && q==size(seq)-1)
                break;
            }

            //checking the size of subsequence and previous sequence

            if(size(pvrseq)<size(subseq)) {

                 for(int y = 0; y<subseq.length; y++)
                 pvrseq[y] = subseq[y];

                 for(int y = 1; y<subseq.length; y++)
                 subseq[y] = 0;
            }
            a++;
        }           
    }

    return size(pvrseq);
  }

  public static void main(String [] args) {
    DivSeq obj = new DivSeq();
    obj.accept();
    System.out.println(obj.sequence());
  }

}

Этот код решает некоторые тестовые случаи, которые он должен решать.

вариант 1: 2,3,7,8,14,39,145,76,320 желаемый результат = 3

вариант 2: 2,11,16,12,36,60,71,17, 29,144,288,129,432,993 желаемый результат = 5

Остальные тестовые примеры невидимы.

Однако это не решает все из них, и я не могу понять, почему.Ему удается удовлетворить только 4/11 тестовых случаев (включая случай 1 и случай 2).

Answer 1

@ LuCio и @Aldert Я нашел альтернативный способ решения проблемы.Вот код:

    import java.util.Scanner;

    class DivSeqUpdated {

      private int n, input[], weight[];

      void accept() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        input = new int[n];
        weight = new int[n];
        for(int i = 0; i<n; i++)
        input[i] = sc.nextInt();
        sc.close();
      }

      int max(int x, int y) {
        return x<y?y:x;
      }

      int sequence(int src, int a[], int n) {
        if(weight[src]==-1) {
            int i, tmp = 0;
            for(i = src+1; i<n; i++) {
                if(a[i]%a[src]==0)
                tmp = max(tmp, sequence(i,a,n));
            }
            weight[src] = tmp+1;
        }
        return weight[src];
      }

      public static void main(String [] args) {
        DivSeqUpdated obj = new DivSeqUpdated();
        obj.accept();
        for(int i = 0; i<obj.n; i++)
        obj.weight[i] = -1;
        int tmp = 0;
        for(int i = 0; i<obj.n; i++) 
        tmp = obj.max(tmp, obj.sequence(i,obj.input,obj.n));
        System.out.println(tmp);
      }    

  }

Это дает результат 11/11 тестов, который решает проблему.Я надеюсь, что это может помочь и другим пользователям.

Answer 2

Я бы использовал рекурсивный подход для определения самой длинной подпоследовательности последовательности.

  protected static int[] subsequence(int[] seq) {
    int[] longestSub = new int[0];
    for (int i = 0; i < seq.length; i++) {
      int[] subAtI = subseq(subarray(seq, i));
      if (longestSub.length < subAtI.length) {
        longestSub = subAtI;
      }
    }
    return longestSub;
  }

  private static int[] subseq(int[] seq) {
    if (seq.length == 1) {
      return seq;
    }

    int[] longestSub = new int[0];
    int current = seq[0];
    for (int i = 1; i < seq.length; i++) {
      int number = seq[i];
      if (number > 0 && current > 0 && number % current == 0) {
        int[] subAtI = subseq(subarray(seq, i));
        if (longestSub.length < subAtI.length) {
          longestSub = subAtI;
        }
      }
    }

    return concat(current, longestSub);
  }

  private static int[] concat(int current, int[] sub) {
    int[] result = new int[sub.length + 1];
    result[0] = current;
    System.arraycopy(sub, 0, result, 1, sub.length);
    return result;
  }

  private static int[] subarray(int[] seq, int i) {
    int length = seq.length - i;
    int[] result = new int[length];
    System.arraycopy(seq, i, result, 0, length);
    return result;
  }

Для последовательности выполните итерацию по каждому целому числу (seq[i]) и определите подпоследовательность для этого целого числа (subsequence(subarray(seq, i))).Самая длинная подпоследовательность - это результат.

Применяя это к какому-то примеру из вопроса:

  public static void main(String[] args) throws IOException {
    printLongestSub(new int[] { 2, 11, 16, 12, 36, 60, 71, 17, 29, 144, 288, 129, 432, 993 }); // [2, 12, 36, 144, 288]
    printLongestSub(new int[] { 2, 3, 7, 8, 14, 39, 145, 76, 320 }); // [2, 8, 320]
    printLongestSub(new int[] { 2 }); // [2]
    printLongestSub(new int[] { 2, 5 }); // [2]
    printLongestSub(new int[] { 5, 6, 12 }); // [6, 12]
    printLongestSub(new int[] { 5, 6, 12, 11, 33, 99 }); // [11, 33, 99]
  }

  private static void printLongestSub(int[] seq) {
    System.out.println(Arrays.toString(subsequence(seq)));
  }