t*****j
发帖数: 1105 | 1 一个array里面，求最长递增子array的算法，除了careerup里面答案给
树的算法以外，还有没有其他更好的算法了？谢谢！ | a****n
发帖数: 1887 | 2 连续的还是不连续的？
Refer to: Longest increasing subsequence & Dynamic Programming | t*****j
发帖数: 1105 | 3 不连续的....如果是连续的话很简单吧，两个指针不就够了？
【在 a****n 的大作中提到】
: 连续的还是不连续的？
: Refer to: Longest increasing subsequence & Dynamic Programming
| a****n
发帖数: 1887 | | t*****j
发帖数: 1105 | | f****g
发帖数: 313 | 6 Refer the "Program Pearl" Chapter 8.
The whole chapter is about how to approach this problem. It gives 4
solutions from O(n^3) to O(n). | c******a
发帖数: 789 | 7 There's also an O(nlogn) solution based on some observations. Let A{i,j} be
the smallest possible tail out of all increasing subsequences of length j
using elements {a1, a2, a3, ..., ai}.
Observe that, for any particular i, A{i,1} < A{i,2} < ... < A{i,j}. This suggests that if we want the longest subsequence that ends with a i + 1, we only need to look for a j such that Ai,j < ai + 1 < = Ai,j + 1 and the length will be j + 1.
Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai +1,k will be equal to Ai,k for k != (j + 1).
Furthermore, there is at most one difference between the set Ai and the set Ai + 1, which is caused by this search.
Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single a1, a2,..., an.
i,j都是小字体，唉，凑合着看吧。 | E********a
发帖数: 124 | | c******a
发帖数: 789 | | p********7
发帖数: 549 | 10 我觉得不可能是O(N),最佳是N*logN
【在 f****g 的大作中提到】
: Refer the "Program Pearl" Chapter 8.
: The whole chapter is about how to approach this problem. It gives 4
: solutions from O(n^3) to O(n).
| t*****j
发帖数: 1105 | 11 我也这么觉得，不过还没时间看那个算法。
这么多热心人....谢谢啊！
【在 p********7 的大作中提到】
: 我觉得不可能是O(N),最佳是N*logN
| f****g
发帖数: 313 | 12 I check the book again, and the best algorithm is in O(n), haha
Here is the pseudo code copied from "Programming Pearl"
maxsofar = 0;
maxendinghere = 0;
for i = [0,n)
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
the run time is O(n). It is DP problem.
Let me know if you still have any question about it:S
【在 p********7 的大作中提到】
: 我觉得不可能是O(N),最佳是N*logN
| z****n
发帖数: 1379 | 13 。。。这个是和最大的连续子集。。。
那个是最常递增子序列
【在 f****g 的大作中提到】
: I check the book again, and the best algorithm is in O(n), haha
: Here is the pseudo code copied from "Programming Pearl"
: maxsofar = 0;
: maxendinghere = 0;
: for i = [0,n)
: maxendinghere = max(maxendinghere + x[i], 0)
: maxsofar = max(maxsofar, maxendinghere)
: the run time is O(n). It is DP problem.
: Let me know if you still have any question about it:S
| f****g
发帖数: 313 | 14 you are right:D, and I am just thinking completely different problem :(
I like the following solution a lot, and it reconstructs the problem as a directed graph
, very simple and straightforward :D
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
【在 z****n 的大作中提到】
: 。。。这个是和最大的连续子集。。。
: 那个是最常递增子序列
|
|
