I wrote some python code that extracts the longest non-decreasing subsequence from any given sequence.

This runs in O(n log n) time, and uses O(n) memory.

''' An item in the final sequence, used to form a linked list. ''' class SeqItem(): val = 0 # This item's value. prev = None # The value before this one. def __init__(self, val, prev): self.val = val self.prev = prev ''' Extract longest non-decreasing subsequence from sequence seq.''' def extract_sorted(seq): subseqs = [SeqItem(seq[0], None)] # Track decreasing subsequences in seq. result_list = [subseqs[0]] for i in range(1, len(seq)): result = search_insert(subseqs, seq[i], 0, len(subseqs)) # Build Python list from custom linked list: final_list = [] result = subseqs[-1] # Longest nondecreasing subsequence is found by # traversing the linked list backwards starting from # the final smallest value in the last nonincreasing # subsequence found. while(result != None and result.val != None): final_list.append(result.val) result = result.prev # Walk backwards through longest sequence. final_list.reverse() return final_list ''' Seq tracks the smallest value of each nonincreasing subsequence constructed. Find smallest item in seq that is greater than search_val. If such a value does not exist, append search_val to seq, creating the beginning of a new nonincreasing subsequence. If such a value does exist, replace the value in seq at that position, and search_val will be considered the new candidate for the longest subseq if a value in the following nonincreasing subsequence is added. Seq is guaranteed to be in increasing sorted order. Returns the index of the element in seq that should be added to results. ''' def search_insert(seq, search_val, start, end): median = (start + end)/2 if end - start < 2: # End of the search. if seq[start].val > search_val: if start > 0: new_item = SeqItem(search_val, seq[start - 1]) else: new_item = SeqItem(search_val, None) seq[start] = new_item return new_item else: # seq[start].val <= search_val if start + 1 < len(seq): new_item = SeqItem(search_val, seq[start]) seq[start + 1] = new_item return new_item else: new_item = SeqItem(search_val, seq[start]) seq.append(new_item) return new_item if search_val < seq[median].val: # Search left side return search_insert(seq, search_val, start, median) else: #search_val >= seq[median].val: # Search right side return search_insert(seq, search_val, median, end)

And here is an example usage:

import random if __name__ == '__main__': seq = [] for i in range(100000): seq.append(int(random.random() * 1000)) print extract_sorted(seq)

Yo, this shit doesn’t fucking work

Can you be a little bit more specific?

E.g., tell me a sequence that this algorithm doesn’t work on.

I have verified this against a few million random strings which were solved using a more brute force approach, so I’d be surprised if there is an error.

Hey,

that was (nearly) excact what i was looking for. Had to write this for univerisity in Java. In the end my resulting code looks MUCH different and is not as fast as yours, but its still okay. Without your example I would have never find a solution (and it took only 3 Hours of try-and-error to understand, how it works ^^)

Thanks for sharing, man.

Hey someone found a

usefor this?! Well, that’s more than I expected when posting itNice to know it’s here if I ever need it. I like the format of the listing too (fixed pitch, alternating shading).

Pingback: Problem Solving: Growing Sequences « My Trip Through CSC165

This problem with your algorithm is not applicable.

Write an algorithm which reads a sequence of real numbers and determines the length of the longest non-decreasing subse-

quence. For instance, in the sequence

7,8,7,8,9,2,1,8,7,9,9,10,10,9,

the longest non-decreasing subsequence is 7,9,9,10,10, of length 5.

@Thanh: It’s trivial to modify the algorithm I gave to produce the longest non-decreasing subsequence, instead of the longest increasing subsequence. In fact, I think it’s just a matter of changing/adding a few characters. What application do you have in mind by the way? I had no application in mind when solving this problem — a professor of mine claimed to have an O(n^2) solution, so I produced an O(n log n) algorithm in response.

Thanks a whole lot for this great post on adjustable piano bench. I will keep it mind when I am searching for a piano seat..

I have to express appreciation to you just for bailing me out of this particular instance. As a result of looking throughout the the net and obtaining notions which are not powerful, I believed my entire life was well over. Existing without the presence of solutions to the issues you have fixed by means of your entire review is a serious case, as well as the ones which might have negatively affected my career if I hadn’t come across your website. Your personal training and kindness in handling every aspect was tremendous. I’m not sure what I would have done if I hadn’t encountered such a step like this. I’m able to at this time look forward to my future. Thanks for your time so much for this skilled and results-oriented help. I won’t be reluctant to suggest your web page to anybody who desires counselling about this issue.