所有最长递增子序列号序列号、最长
我练的算法和我的任务之一就是计数若干所有最长递增子序列对于给定的 0℃ N'LT = 10 ^ 6 的数字。解决方案的为O（n ^ 2）的是不是一种选择。
我已经执行找到一个LIS，其长度（ LIS算法 ），但这种算法切换编号，以最低可能的。因此，这是不可能的，以确定是否子序列与previous号（大的）将能够达到最长的长度，否则我可以指望那些开关，我猜。
任何想法如何得到这个关于 O（nlogn）？我知道应该用动态规划解决。
我实现了一个解决方案，它工作得很好，但它需要两个嵌套循环的（我在1..N）×（法官在1..i-1）的。照片 因此，它的为O（n ^ 2）的，我认为，尽管如此，它的速度太慢。
我想甚至将这些数字从数组到一个二叉树（因为每个的我的迭代我期待所有的小数字，然后的号[I] 的 - 经历元素的 I-1..1 的），但它更慢。
例测试：
1 3 2 2 4
结果：3（1,3,4 | 1,2,4 | 1,2,4）
3 2 1
结果：3（1 | 2 | 3）
16 5 8 6 1 10 5 2 15 3 2 4 1
结果：3（5,8,10,15 | 5,6,10,15 | 1,2,3,4）
解决方案
查找所有最长递增子序列的数量
改进LIS算法，它发现最长递增子不仅长度，但这样的长度的子序列的数目的全爪哇code，在下面。我preFER使用泛型允许不仅是整数，但任何类似的类型。
@Test
公共无效testLisNumberAndLength（）{
名单＆LT;整数GT;输入= Arrays.asList（16，5,8，6，1，10，5,2，15，3，2，4，1）;
INT []结果= lisNumberAndlength（输入）;
的System.out.println（的String.Format（
这个序列具有％，最长的长度增加的％s subsequenses
导致[0]，结果[1]
））;
}
/ **
*改进LIS算法的身体
* /
公众＆LT;吨延伸可比＆LT; T＆GT;＆GT; INT [] lisNumberAndLength（名单＆LT; T＆GT;输入）{
如果（input.size（）== 0）
返回新INT [] {0,0};
名单＆LT;列表＆lt;副＆LT; T＆GT;＆GT;＆GT;潜艇=新的ArrayList＆LT;＆GT;（）;
名单＆lt;副＆LT; T＆GT;＆GT;尾部=新的ArrayList＆LT;＆GT;（）;
对于（T E：输入）{
INT POS =搜索（尾巴，新的子＆LT;＆GT;（E，0），FALSE）; //行一个新的子放置
INT总和= 1;
如果（POS大于0）{
名单＆lt;副＆LT; T＆GT;＆GT;船头= subs.get（POS - 1）; // previous行
INT指数=搜索（船头，新的子＆LT; T＆GT;（E，0），TRUE）; //指数最左边的元素是＆LT; = E
如果（pRow.get（指数）.value.compareTo（E）℃，）{
指数 - ;
}
总和= pRow.get（pRow.size（） - 1）.SUM; //尾部元素在previous行和
如果（索引＆gt; = 0）{
总和 - = pRow.get（指数）.SUM;
}
}
如果（POS＆GT; = subs.size（））{//添加一个新行
名单＆lt;副＆LT; T＆GT;＆GT;行=新的ArrayList＆LT;＆GT;（）;
row.add（新的子＆LT;＆GT;（五，总和））;
subs.add（行）;
tails.add（新的子＆LT;＆GT;（E，0））;
}其他{//添加子到现有的行
名单＆lt;副＆LT; T＆GT;＆GT;行= subs.get（POS）;
子＆LT; T＆GT;尾= row.get（row.size（） - 1）;
如果（tail.value.equals（E））{
tail.sum + =总和;
} 其他 {
row.add（新的子＆LT;＆GT;（五，tail.sum +总和））;
tails.set（POS，新的子＆LT;＆GT;（E，0））;
}
}
}
名单＆lt;副＆LT; T＆GT;＆GT; LASTROW = subs.get（subs.size（） - 1）;
子＆LT; T＆GT;最后= lastRow.get（lastRow.size（） - 1）;
返回新INT [] {last.sum，subs.size（）};
}
/ **
*二进制搜索的排序列表实现
* /
公众＆LT; T＆GT; INT搜索（表＆LT ;?延伸可比＆LT; T＆GT;＆GT; A，T V，布尔型反转）{
如果（a.size（）== 0）
返回0;
INT标志=逆转吗？ -1：1;
INT右= a.size（） - 1;
可比＆LT; T＆GT; vRight = a.get（右）;
如果（vRight.compareTo（ⅴ）*符号℃下）
返回家园的权利+ 1;
INT左= 0;
INT POS = 0;
可比＆LT; T＆GT; VPOS;
可比＆LT; T＆GT; vLeft = a.get（左）;
对于（;;） {
如果（右 - 左＆LT; = 1）{
如果（vRight.compareTo（ⅴ）*符号＆GT; = 0＆安培;＆安培; vLeft.compareTo（ⅴ）*符号℃下）
返回的权利;
其他
返回左;
}
POS =（左+右）＆GT;＆GT;＆GT; 1;
VPOS = a.get（POS）;
如果（vPos.equals（ⅴ））{
返回POS机;
}否则如果（vPos.compareTo（ⅴ）*符号大于0）{
右= POS机;
vRight = VPOS;
} 其他 {
左= POS机;
vLeft = VPOS;
}
}
}
/ **
*为'子'对班
* /
公共静态类子＆LT;吨延伸可比＆LT; T＆GT;＆GT;实现可比＆lt;副＆LT; T＆GT;＆GT; {
t值;
INT总和;
公众子（吨价，INT和）{
THIS.VALUE =价值;
this.sum =总和;
}
@覆盖公共字符串的toString（）{
返回的String.Format（（％S，％S），价值之和）;
}
@覆盖公众诠释的compareTo（子＆LT; T＆GT;另一个）{
返回this.value.compareTo（another.value）;
}
}
说明
由于我的解释似乎很长，我会打电话给初始序列序列，并任其子的子。因此任务是计算，可以从以下各获得最长增加潜艇的计数
正如我之前提到的，思想是保持获得的previous步骤所有可能的最长的潜艇数量。因此，让我们创建行，其中的的编号列表中的每个行的数量等于潜艇存储在该行的在长度。而且，我们店潜艇为双数（V，C），其中V是的值结束元素的的，C是的定长度的潜艇为此的数由v的的。例如：
1：（16，1）//这意味着，到目前为止，我们有1子长度1，它由16结束了。
我们将逐步建立这样的清单一步，由他们接订单从最初的序列元件。在每个步骤中，我们将尽力为这个元素添加到最长子，它可以添加到并记录更改。
建立一个名单
让我们使用顺序，从你的榜样生成列表，因为它有所有可能的选择：
16 5 8 6 1 10 5 2 15 3 2 4 1
首先，考虑元素的 16 。我们的列表是空的，到目前为止，所以我们只是把一对在里面：
1：（16，1） - = =一个子，到16结束
接下来是 5 。它不能被添加到了16结束一分，所以它会创建新的子带1的长度我们创建了一个对（5,1），放入1号线：
1：（16，1）（5,1）
元素的 8 即将在下。它不能创建长度2的副[16,8]，但可以创建子[5,8]。所以，这就是算法来了。首先，我们遍历列表行倒挂，看着最后一对的价值。如果我们的元素大于在所有行的所有最后元素的值，那么我们就可以将其添加到现有的子（S），由一个增加它的长度。所以值8将创建列表的新行，因为它大于值存在于该列表中到目前为止所有最后元件（即> 5）：
1：（16，1）（5,1）
2：（？8）＆LT; ===需要解决多少个8结尾的最长的潜艇可以得到
元素8可以继续5，但不能继续16.因此，我们需要通过previous行搜索，从年底开始，计算计数的总和对，其价值小于8：
（16，1）（5,1）^ //总和= 0
（16，1）^（5，1）//总和= 1
^（16，1）（5，1）//值16取代; = 8：停止。数=总和= 1，所以写1对旁边8
1：（16，1）（5，1）
2：（8,1）＆LT; ===到目前为止，我们有1子长度2其8结尾的。
我们为什么不储存价值8成的长度1（第一行）的潜艇？因为我们需要尽可能长的潜艇和8可以继续一些previous潜艇。所以每下一个数大于8也将继续这样的子，并且没有必要保持8作为长度子较少，它可以是
下一步。 6 。行搜索倒挂最后的价值观：
1：（16，1）（5，1） - =; === 5℃ 6，去旁边
2：（8,1）
1：（16，1）（5，1）
2：（8，1） - ; === 8'= 6，所以6此处应该放
发现房间6，需要计算计数：
拿previous线
（16，1）（5，1）^ //总和= 0
（16，1）^（5，1）// 5℃ 6：总和= 1
^（16，1）（5，1）// 16取代; = 6：停止，写计数=总和= 1
1：（16，1）（5，1）
2：（8,1）（6,1）
加工后的 1
1：（16，1）（5,1）（1,1）＆LT; ===
2：（8,1）（6,1）
加工后的 10
1：（16，1）（5,1）（1,1）
2：（8,1）（6,1）
3：（10，2）＆其中; ===计数为2，因为两个值8和6从previous行小于10，因此，我们总结其计数：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）
如果当最后一个元素搜索列，我们发现相同的元素，我们计算出它的倒计基础上再次previous行，并添加到现有的计数。
加工后的 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）＆LT; ===
2：（8,1）（6,1）（5,1）（2，2）
3：（10，2）（3，1）
4：（15，2）（4，1）
那我们处理所有的初始序列后有哪些？看着最后一排，我们可以看到，我们有3个最长的潜艇，分别由4个要素：4 2月底15和1结束
有关的复杂性是什么？
在每次迭代，即从初始序列下一个元素的时候，我们做2个循环：首先总结了previous行数时，迭代行时找房的下一个元素，而第二位。因此，对于每一个元素，我们最大程度地为 N 迭代（最坏的情况下：如果初始序列由按升序排列元素，我们将得到N行列表1对每一行中;如果序列进行排序降序排序，我们将获得1排有n个元素的列表）。顺便说一句，为O（n 2 ）的复杂性是不是我们想要的。
首先，这是显而易见的，在每一个中间状态行增加了他们最后的价值的顺序进行排序。因此，而不是蛮力环，二分查找可以进行的，这复杂度为O（log n）的。
其次，我们不需要通过行元素每次循环总结潜艇的罪状。我们可以在过程概括它们，当一对新加入到该行，这样的：
的 1：（16，1）（5,2）＆其中; ===代替1，把previous元件1+计数的行中
所以，第二个数字将显示不的计数的，可以与给定值在年底获得最长的潜艇，但是的的结束所有最长的潜艇的摘要计数的由一个大于或等于从一对价值的任何元素。的
因此，计数将被总和所取代。而不是在previous行迭代元素和，我们只是执行二进制搜索（这是可能的，因为在任何行对通过它们的价值总是订购），以之新对作为最后一个元素的总和在previous行减去元素求和的当前行中留给发现位置在previous行previous元素加总和。
所以，当处理的 4
1：（16，1）（5,2）（1,3）
2：（8,1）（6,2）（5,3）（2，5）
3：（10，2）（3，3）
4：;（？4，）（15，2）及所述===余地
在连续3个搜索的价值与LT; 4：
3：（10，2）^（3,3）
4，将搭配（3-2 + 2）：（求和，从最后一对previous行） - （森从对左对发现的位置在previous行）+ （由previous对当前行总和）：
4：（15,2）（4,3）
在这种情况下，所有的最长潜艇的最后数为总和从最后一对的列表中的最后一排的岛。即3，不是3 + 2
所以，这两个行搜索和搜索之执行二进制搜索，我们的将带着为O（n * log n）的复杂性。
怎么样的内存占用，处理所有的数组后，我们获得最大的N对，所以内存消耗情况动态数组将是为O（n）。此外，使用动态数组或集合时，一些额外的时间是需要的分配和调整它们的大小，但大多数操作是由在O（1）时间，因为我们不作任何形式的过程中，排序和重排。因此，复杂性估计似乎是最终的。
I'm practicing algorithms and one of my tasks is to count the number of all longest increasing sub-sequences for given 0 < n <= 10^6 numbers. Solution O(n^2) is not an option.
I have already implemented finding a LIS and its length (LIS Algorithm), but this algorithm switches numbers to the lowest possible. Therefore, it's impossible to determine if sub-sequences with a previous number (the bigger one) would be able to achieve the longest length, otherwise I could just count those switches, I guess.
Any ideas how to get this in about O(nlogn)? I know that it should be solved using dynamic-programming.
I implemented one solution and it works well, but it requires two nested loops (i in 1..n) x (j in 1..i-1). So it's O(n^2) I think, nevertheless it's too slow.
I tried even to move those numbers from array to a binary tree (because in each i iteration I look for all smaller numbers then number[i] - going through elements i-1..1), but it was even slower.
Example tests:
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)
解决方案
Finding the number of all longest increasing subsequences
Full Java code of improved LIS algorithm, which discovers not only the length of longest increasing subsequence, but number of subsequences of such length, is below. I prefer to use generics to allow not only integers, but any comparable types.
@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);
}
}
Explanation
As my explanation seems to be long, I will call initial sequence "seq" and any its subsequence "sub". So the task is to calculate count of longest increasing subs that can be obtained from the seq.
As I mentioned before, idea is to keep counts of all possible longest subs obtained on previous steps. So let's create a numbered list of rows, where number of each line equals the length of subs stored in this row. And let's store subs as pairs of numbers (v, c), where "v" is "value" of ending element, "c" is "count" of subs of given length that end by "v". For example:
1: (16, 1) // that means that so far we have 1 sub of length 1 which ends by 16.
We will build such list step by step, taking elements from initial sequence by their order. On every step we will try to add this element to the longest sub that it can be added to and record changes.
Building a list
Let's build the list using sequence from your example, since it has all possible options:
16 5 8 6 1 10 5 2 15 3 2 4 1
First, take element 16. Our list is empty so far, so we just put one pair in it:
1: (16, 1) <= one sub that ends by 16
Next is 5. It cannot be added to a sub that ends by 16, so it will create new sub with length of 1. We create a pair (5, 1) and put it into line 1:
1: (16, 1)(5, 1)
Element 8 is coming next. It cannot create the sub [16, 8] of length 2, but can create the sub [5, 8]. So, this is where algorithm is coming. First, we iterate the list rows upside down, looking at the "values" of last pair. If our element is greater than values of all last elements in all rows, then we can add it to existing sub(s), increasing its length by one. So value 8 will create new row of the list, because it is greater than values all last elements existing in the list so far (i. e. > 5):
1: (16, 1)(5, 1)
2: (8, ?) <=== need to resolve how many longest subs ending by 8 can be obtained
Element 8 can continue 5, but cannot continue 16. So we need to search through previous row, starting from its end, calculating the sum of "counts" in pairs which "value" is less than 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.
Why don't we store value 8 into subs of length 1 (first line)? Because we need subs of maximum possible length, and 8 can continue some previous subs. So every next number greater than 8 will also continue such sub and there is no need to keep 8 as sub of length less that it can be.
Next. 6. Searching upside down by last "values" in rows:
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
Found the room for 6, need to calculate a count:
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)
After processing 1:
1: (16, 1)(5, 1)(1, 1) <===
2: (8, 1)(6, 1)
After processing 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
After processing 5:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1) <===
3: (10, 2)
After processing 2:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1) <===
3: (10, 2)
After processing 15:
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)
4: (15, 2) <===
After processing 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)
After processing 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)
If when searching rows by last element we find equal element, we calculate its "count" again based on previous row, and add to existing "count".
After processing 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) <===
After processing 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)
So what do we have after processing all initial sequence? Looking at the last row, we see that we have 3 longest subs, each consist of 4 elements: 2 end by 15 and 1 ends by 4.
What about complexity?
On every iteration, when taking next element from initial sequence, we make 2 loops: first when iterating rows to find room for next element, and second when summarizing counts in previous row. So for every element we make maximum to n iterations (worst cases: if initial seq consists of elements in increasing order, we will get a list of n rows with 1 pair in every row; if seq is sorted in descending order, we will obtain list of 1 row with n elements). By the way, O(n2) complexity is not what we want.
First, this is obvious, that in every intermediate state rows are sorted by increasing order of their last "value". So instead of brute loop, binary searching can be performed, which complexity is O(log n).
Second, we don't need to summarize "counts" of subs by looping through row elements every time. We can summarize them in process, when new pair is added to the row, like:
1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row
So second number will show not count of longest subs that can be obtained with given value at the end, but summary count of all longest subs that end by any element that is greater or equal to "value" from the pair.
Thus, "counts" will be replaced by "sums". And instead of iterating elements in previous row, we just perform binary search (it is possible because pairs in any row are always ordered by their "values") and take "sum" for new pair as "sum" of last element in previous row minus "sum" from element left to found position in previous row plus "sum" of previous element in the current row.
So when processing 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 will be paired with (3-2+2): ("sum" from the last pair of previous row) - ("sum" from pair left to found position in previous row) + ("sum" from previous pair in current row):
4: (15, 2)(4, 3)
In this case, final count of all longest subs is "sum" from the last pair of the last row of the list, i. e. 3, not 3 + 2.
So, performing binary search to both row search and sum search, we will come with O(n*log n) complexity.
What about memory consumed, after processing all array we obtain maximum n pairs, so memory consumption in case of dynamic arrays will be O(n). Besides, when using dynamic arrays or collections, some additional time is needed to allocate and resize them, but most operations are made in O(1) time because we don't make any kind of sorting and rearrangement during process. So complexity estimation seems to be final.
