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

下面是改进的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”。因此，任务是计算可以从序列中获得的最长递增子的计数。

正如我之前提到的，想法是保持对在先前步骤中获得的所有可能的最长子计数。因此，让我们创建一个行编号列表，其中每行的数量等于存储在该行中的子程序的长度。然后将潜艇存储为数字对（v，c），其中“ v”是结束元素的“值”，“ c”是给定长度的潜艇的“计数”，这些潜艇以“ v”结尾。例如：

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)  

如果在按最后一个元素搜索行时发现相等的元素，那么我们将根据前一行再次计算其“计数”，然后添加到现有的“计数”中。

经过处理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）。

其次，我们不需要每次都通过遍历行元素来总结子的“计数”。当将新的配对添加到行中时，我们可以对它们进行汇总，例如：

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）时间内完成的，因为我们在处理过程中不进行任何排序和重新排列。因此，复杂度估计似乎是最终的。