所有增长最长的子序列的数量

Question

我正在练习算法,我的任务之一是计算给定0 <n <= 10 ^ 6个数字的所有最长增长子序列的数量.解决方案O(n ^ 2)不是一个选项.

我已经实现了查找LIS及其长度(LIS算法),但是该算法将数字切换到尽可能低的数字.因此,我不可能确定具有先前数字(较大的数字)的子序列是否能够实现最长的长度,否则我可以计算这些开关.

任何关于如何在O(nlogn)中得到这个的想法？我知道它应该使用动态编程来解决.

我实现了一个解决方案,它运行良好,但它需要两个嵌套循环(i in 1..n)x(j in 1..i-1).
所以它是O(n ^ 2)我认为,但它太慢了.

我试图甚至那些从数字阵列移动到一个二叉树(因为在每次我迭代i寻找所有更小的数字,然后数[I] -经历元件I-1..1),但它是更慢.

示例测试:

1 3 2 2 4
result: 3 (1,3,4 | 1,2,4 | 1,2,4)

3 2 1
result: 3 (1 | 2 | 3)

16 5 8 6 1 10 5 2 15 3 2 4 1
result: 3 (5,8,10,15 | 5,6,10,15 | 1,2,3,4)

Answer 1

查找所有最长的增加子序列的数量

改进的LIS算法的完整Java代码,其不仅发现最长增加子序列的长度,而且发现这种长度的子序列的数量,如下.我更喜欢使用泛型来不仅允许整数,而且允许任何类似的类型.

@Test
public void testLisNumberAndLength() {

    List<Integer> input = Arrays.asList(16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1);
    int[] result = lisNumberAndlength(input);
    System.out.println(String.format(
            "This sequence has %s longest increasing subsequenses of length %s", 
            result[0], result[1]
            ));
}


/**
 * Body of improved LIS algorithm
 */
public <T extends Comparable<T>> int[] lisNumberAndLength(List<T> input) {

    if (input.size() == 0) 
        return new int[] {0, 0};

    List<List<Sub<T>>> subs = new ArrayList<>();
    List<Sub<T>> tails = new ArrayList<>();

    for (T e : input) {
        int pos = search(tails, new Sub<>(e, 0), false);      // row for a new sub to be placed
        int sum = 1;
        if (pos > 0) {
            List<Sub<T>> pRow = subs.get(pos - 1);            // previous row
            int index = search(pRow, new Sub<T>(e, 0), true); // index of most left element that <= e
            if (pRow.get(index).value.compareTo(e) < 0) {
                index--;
            } 
            sum = pRow.get(pRow.size() - 1).sum;              // sum of tail element in previous row
            if (index >= 0) {
                sum -= pRow.get(index).sum;
            }
        }

        if (pos >= subs.size()) {                             // add a new row
            List<Sub<T>> row = new ArrayList<>();
            row.add(new Sub<>(e, sum));
            subs.add(row);
            tails.add(new Sub<>(e, 0));

        } else {                                              // add sub to existing row
            List<Sub<T>> row = subs.get(pos);
            Sub<T> tail = row.get(row.size() - 1); 
            if (tail.value.equals(e)) {
                tail.sum += sum;
            } else {
                row.add(new Sub<>(e, tail.sum + sum));
                tails.set(pos, new Sub<>(e, 0));
            }
        }
    }

    List<Sub<T>> lastRow = subs.get(subs.size() - 1);
    Sub<T> last = lastRow.get(lastRow.size() - 1);
    return new int[]{last.sum, subs.size()};
}



/**
 * Implementation of binary search in a sorted list
 */
public <T> int search(List<? extends Comparable<T>> a, T v, boolean reversed) {

    if (a.size() == 0)
        return 0;

    int sign = reversed ? -1 : 1;
    int right = a.size() - 1;

    Comparable<T> vRight = a.get(right);
    if (vRight.compareTo(v) * sign < 0)
        return right + 1;

    int left = 0;
    int pos = 0;
    Comparable<T> vPos;
    Comparable<T> vLeft = a.get(left);

    for(;;) {
        if (right - left <= 1) {
            if (vRight.compareTo(v) * sign >= 0 && vLeft.compareTo(v) * sign < 0) 
                return right;
            else 
                return left;
        }
        pos = (left + right) >>> 1;
        vPos = a.get(pos);
        if (vPos.equals(v)) {
            return pos;
        } else if (vPos.compareTo(v) * sign > 0) {
            right = pos;
            vRight = vPos;
        } else {
            left = pos;
            vLeft = vPos;
        }
    } 
}



/**
 * Class for 'sub' pairs
 */
public static class Sub<T extends Comparable<T>> implements Comparable<Sub<T>> {

    T value;
    int sum;

    public Sub(T value, int sum) { 
        this.value = value; 
        this.sum = sum; 
    }

    @Override public String toString() {
        return String.format("(%s, %s)", value, sum); 
    }

    @Override public int compareTo(Sub<T> another) { 
        return this.value.compareTo(another.value); 
    }
}

说明

由于我的解释似乎很长,我将调用初始序列"seq"及其子序列"sub".因此,任务是计算可从seq获得的最长增长潜艇的计数.

正如我之前提到的,想法是保留前面步骤中获得的所有可能最长的潜艇的计数.因此,让我们创建一个编号的行列表,其中每行的数量等于该行中存储的subs的长度.并且让我们将subs存储为数字对(v,c),其中"v"是结束元素的"值","c"是以"v"结尾的给定长度的subs的"count".例如:

1: (16, 1) // that means that so far we have 1 sub of length 1 which ends by 16.

我们将逐步构建这样的列表,按顺序从初始序列中获取元素.在每一步中,我们都会尝试将此元素添加到可以添加到其中的最长子元素并记录更改.

建立一个清单

让我们使用您示例中的序列构建列表,因为它具有所有可能的选项:

 16 5 8 6 1 10 5 2 15 3 2 4 1

首先,采取要素16.到目前为止,我们的列表是空的,所以我们只在其中放入一对:

1: (16, 1) <= one sub that ends by 16

接下来是5.它不能添加到以16结尾的子,因此它将创建长度为1的新子.我们创建一对(5,1)并将其放入第1行:

1: (16, 1)(5, 1)

元素8接下来.它不能创建长度为2的子[16,8],但可以创建子[5,8].所以,这就是算法的来源.首先,我们颠倒列表行,查看最后一对的"值".如果我们的元素大于所有行中所有最后元素的值,那么我们可以将它添加到现有子元素,将其长度增加一.因此,值8将创建列表的新行,因为它大于目前列表中存在的所有最后元素的值(即> 5):

1: (16, 1)(5, 1) 
2: (8, ?)   <=== need to resolve how many longest subs ending by 8 can be obtained

元素8可以继续5,但不能继续16.所以我们需要搜索前一行,从结束开始,计算"值"小于8的"计数"总和:

(16, 1)(5, 1)^  // sum = 0
(16, 1)^(5, 1)  // sum = 1
^(16, 1)(5, 1)  // value 16 >= 8: stop. count = sum = 1, so write 1 in pair next to 8

1: (16, 1)(5, 1)
2: (8, 1)  <=== so far we have 1 sub of length 2 which ends by 8.

为什么我们不将值8存储到长度为1(第一行)的子节点中？因为我们需要最大可能长度的子,并且8可以继续一些先前的子.因此,每个大于8的下一个数字也将继续这样的子数,并且不需要保持8作为长度的子数减去它可以.

下一个.6.在行中按最后"值"颠倒搜索:

1: (16, 1)(5, 1)  <=== 5 < 6, go next
2: (8, 1)

1: (16, 1)(5, 1)
2: (8, 1 )  <=== 8 >= 6, so 6 should be put here

找到6个房间,需要计算一个数:

take previous line
(16, 1)(5, 1)^  // sum = 0
(16, 1)^(5, 1)  // 5 < 6: sum = 1
^(16, 1)(5, 1)  // 16 >= 6: stop, write count = sum = 1

1: (16, 1)(5, 1)
2: (8, 1)(6, 1) 

处理完1后:

1: (16, 1)(5, 1)(1, 1) <===
2: (8, 1)(6, 1)

处理完10后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)
3: (10, 2) <=== count is 2 because both "values" 8 and 6 from previous row are less than 10, so we summarized their "counts": 1 + 1

处理完5后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1) <===
3: (10, 2)

处理完2后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1) <===
3: (10, 2)

处理完15后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)
4: (15, 2) <===

处理完3后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)(3, 1) <===
4: (15, 2)  

处理完2后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2) <===
3: (10, 2)(3, 1) 
4: (15, 2)  

如果在按最后一个元素搜索行时我们找到相等的元素,我们将根据前一行再次计算其"计数",并添加到现有的"count".

处理完4后:

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2)  
3: (10, 2)(3, 1) 
4: (15, 2)(4, 1) <===

处理完1后:

1: (16, 1)(5, 1)(1, 2) <===
2: (8, 1)(6, 1)(5, 1)(2, 2)  
3: (10, 2)(3, 1) 
4: (15, 2)(4, 1)  

那么在处理完所有初始序列后我们有什么？看最后一行,我们看到我们有3个最长的潜艇,每个潜艇由4个元件组成:2个结束15个,1个结束4个.

复杂性怎么样？

在每次迭代中,当从初始序列中获取下一个元素时,我们进行2个循环:首先是迭代行以找到下一个元素的空间,第二个是汇总上一行中的计数.因此,对于每个元素,我们最多进行n次迭代(最坏的情况:如果初始seq由按升序排列的元素组成,我们将得到n行的列表,每行有1对;如果seq按降序排序,我们将获得带有n个元素的1行列表).顺便说一句,O(n ²)复杂性不是我们想要的.

首先,显而易见的是,在每个中间状态行中,按照其最后"值"的递增顺序对其进行排序.因此,可以执行二进制搜索而不是暴力循环,其复杂度为O(log n).

其次,我们不需要每次循环遍历行元素来总结subs的"计数".当新的对添加到行中时,我们可以在过程中对它们进行汇总,例如:

1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row

所以第二数量会显示不计数可以与在端部给定值而获得最长潜艇,但是总结计数的通过是大于或等于从所述一对"值"的任何元素结尾的所有最长潜艇.

因此,"计数"将被"总和"取代.而不是迭代上一行中的元素,我们只执行二分搜索(这是可能的,因为任何行中的对总是按其"值"排序)并将新对的"sum"作为前一行中最后一个元素的"sum"减去从左边的元素到前一行中找到的位置的"sum"加上当前行中前一个元素的"sum".

所以当处理4时:

1: (16, 1)(5, 2)(1, 3)
2: (8, 1)(6, 2)(5, 3)(2, 5) 
3: (10, 2)(3, 3) 
4: (15, 2) <=== room for (4, ?)

search in row 3 by "values" < 4:
3: (10, 2)^(3, 3) 

4将与(3-2 + 2)配对:(来自前一行的最后一对的"和") - (从左对齐到前一行中找到的位置的"和")+(当前前一对中的"和")行):

4: (15, 2)(4, 3)

在这种情况下,所有最长潜艇的最终计数是来自列表最后一行的最后一对的"总和",即3,而不是3 + 2.

因此,对行搜索和求和搜索执行二进制搜索,我们将得到O(n*log n)复杂度.

消耗的内存如何,在处理完所有数组之后我们获得最多n对,因此在动态数组的情况下的内存消耗将是O(n).此外,在使用动态数组或集合时,需要一些额外的时间来分配和调整它们,但大多数操作都是在O(1)时间内完成的,因为我们在处理过程中不进行任何类型的排序和重新排列.所以复杂性估计似乎是最终的.