时间戳

首页 > 解决方案 > 我的分割序列代码并不能解决它所面临的所有问题

java - 我的分割序列代码并不能解决它所面临的所有问题

问题描述

这个问题是关于正整数序列 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，其中只要 i < j，ai 就可以整除 aj。例如，3,15,60,720 是一个完全划分的序列。

给定一个整数序列，您的目标是找到该序列的最长完全分割子序列的长度。

考虑序列 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）。

标签： javaarrayssequencedynamic-programming

解决方案

@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 测试结果。我希望这也可以帮助其他用户。

推荐阅读