StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
7918909
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-10-27T16:06:48.380
FavoriteCount
0
LastActivityDate
2011-10-27T16:06:48.380
LastEditDate
LastEditorUserId
0
OwnerUserId
264003
ParentId
3992697
PostTypeId
2
Score
2
ViewCount
0
LastEditorDisplayName
text
Body
<p>Here is some python code with tests which implements the algorithm running in O(n*log(n)). I found this on a the <a href="http://en.wikipedia.org/wiki/Talk%3aLongest_increasing_subsequence" rel="nofollow">wikipedia talk page</a> about the <a href="http://en.wikipedia.org/wiki/Longest_increasing_subsequence" rel="nofollow">longest increasing subsequence</a>. </p> <pre><code>import unittest def LongestIncreasingSubsequence(X): """ Find and return longest increasing subsequence of S. If multiple increasing subsequences exist, the one that ends with the smallest value is preferred, and if multiple occurrences of that value can end the sequence, then the earliest occurrence is preferred. """ n = len(X) X = [None] + X # Pad sequence so that it starts at X[1] M = [None]*(n+1) # Allocate arrays for M and P P = [None]*(n+1) L = 0 for i in range(1,n+1): if L == 0 or X[M[1]] >= X[i]: # there is no j s.t. X[M[j]] < X[i]] j = 0 else: # binary search for the largest j s.t. X[M[j]] < X[i]] lo = 1 # largest value known to be <= j hi = L+1 # smallest value known to be > j while lo < hi - 1: mid = (lo + hi)//2 if X[M[mid]] < X[i]: lo = mid else: hi = mid j = lo P[i] = M[j] if j == L or X[i] < X[M[j+1]]: M[j+1] = i L = max(L,j+1) # Backtrack to find the optimal sequence in reverse order output = [] pos = M[L] while L > 0: output.append(X[pos]) pos = P[pos] L -= 1 output.reverse() return output # Try small lists and check that the correct subsequences are generated. class LISTest(unittest.TestCase): def testLIS(self): self.assertEqual(LongestIncreasingSubsequence([]),[]) self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1]) self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10)) self.assertEqual(LongestIncreasingSubsequence(\ [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]), [1,2,3,5,8,9]) unittest.main() </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POLongest increasing subsequence
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USzzz
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  PO
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.