查找所有最长递增子序列的数量
下面是改进后的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]
));
}
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);
int sum = 1;
if (pos > 0) {
List<Sub<T>> pRow = subs.get(pos - 1);
int index = search(pRow, new Sub<T>(e, 0), true);
if (pRow.get(index).value.compareTo(e) < 0) {
index--;
}
sum = pRow.get(pRow.size() - 1).sum;
if (index >= 0) {
sum -= pRow.get(index).sum;
}
}
if (pos >= subs.size()) {
List<Sub<T>> row = new ArrayList<>();
row.add(new Sub<>(e, sum));
subs.add(row);
tails.add(new Sub<>(e, 0));
} else {
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()};
}
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;
}
}
}
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中获得的最长递增子序列的数量。
正如我之前提到的，想法是保持在先前步骤中获得的所有可能的最长子序列的计数。因此，让我们创建一个带有编号的行列表，其中每行的编号等于存储在该行中的子序列的长度。并且让我们将子序列存储为数字对(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次迭代（最坏情况：如果初始序列按递增顺序排列，我们将得到n行，每行有1对；如果序列按降序排列，则会获得具有n个元素的1行列表）。顺便说一句，O(n²)的复杂度不是我们想要的。
首先，很明显，在每个中间状态下，行都按其最后一个“值”的递增顺序排序。因此，可以执行二进制搜索而不是暴力循环，其复杂度为O(log n)。
其次，我们不需要每次通过循环遍历行元素来汇总子序列的“计数”。我们可以在添加新对到行时的过程中进行汇总，例如：
1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row
因此，第二个数字将显示不是以给定值结尾的最长子序列的计数，而是以“值”对中大于或等于“值”的任何元素结尾的所有最长子序列的摘要计数。
因此，“counts”将被替换为“sums”。我们不再迭代前一行中的元素，而是执行二进制搜索（这是可能的，因为任何行中的对始终按其“值”排序），并将新对的“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)
在这种情况下，最长子串的最终计数是列表的最后一行的最后一对的“sum”，即3，而不是3 + 2。
因此，在进行二分查找时，对行搜索和总和搜索，我们将得到O（n * log n）复杂度。
至于内存消耗，在处理完整个数组后，我们获得最大n对，因此在使用动态数组的情况下，内存消耗为O（n）。此外，当使用动态数组或集合时，需要一些额外的时间来分配和调整它们的大小，但是大多数操作都在O（1）时间内完成，因为我们在过程中不进行任何排序和重新排列。因此，复杂性估计似乎是最终的。
