查找所有最长递增子序列的数量
下面是改进的 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 存储为数字对 (v, c)，其中“v”是结束元素的“值”，“c”是给定长度的以“v”结尾的 subs 的“计数”。例如：
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 结尾的 sub，因此它将创建长度为 1 的新 sub。我们创建一对 (5, 1) 并将其放入第 1 行：
1: (16, 1)(5, 1)
元素8即将到来。它不能创建长度为 2 的子 [16, 8]，但可以创建子 [5, 8]。所以，这就是算法来的地方。首先，我们颠倒迭代列表行，查看最后一对的“值”。如果我们的元素大于所有行中所有最后一个元素的值，那么我们可以将其添加到现有的 sub(s) 中，将其长度增加一。所以值 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（第一行）的 subs 中？因为我们需要最大可能长度的 subs，并且 8 可以继续一些以前的 subs。因此，每个大于 8 的下一个数字也将继续这样的 sub，并且没有必要保持 8 作为 sub 的长度小于它可以的长度。
下一个。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 2 )复杂度不是我们想要的。
首先，这很明显，在每个中间状态中，行都按其最后一个“值”的升序排序。因此，可以执行二进制搜索而不是暴力循环，其复杂度为 O(log n)。
其次，我们不需要通过每次循环遍历行元素来总结 subs 的“计数”。当新的对添加到行中时，我们可以在过程中总结它们，例如：
1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row
因此，第二个数字将不显示可以在最后以给定值获得的最长子项的计数，而是以任何大于或等于该对“值”的元素结尾的所有最长子项的汇总计数。
因此，“计数”将被“总和”取代。而不是迭代前一行中的元素，我们只执行二进制搜索（这是可能的，因为任何行中的对总是按它们的“值”排序）并将新对的“总和”作为前一行中最后一个元素的“总和”从左边的元素减去“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) 配对：（前一行最后一对的“sum”）-（前一行左侧对的“sum”）+（当前前一对的“sum”排）：
4: (15, 2)(4, 3)
在这种情况下，所有最长子项的最终计数是列表最后一行的最后一对的“总和”，即 3，而不是 3 + 2。
因此，对行搜索和求和搜索执行二进制搜索，我们将得到 O(n*log n) 复杂度。
内存消耗怎么样，在处理完所有数组后，我们获得最大 n 对，所以动态数组的内存消耗将是 O(n)。此外，当使用动态数组或集合时，需要一些额外的时间来分配和调整它们的大小，但大多数操作都是在 O(1) 时间内完成的，因为我们在处理过程中没有进行任何类型的排序和重新排列。所以复杂性估计似乎是最终的。