How do I find the longest increasing sub-sequence of integers from a list of integers in C#?

You want what is known as patience sorting. It can compute the length, and find the sequence.

Create three variables: two integer lists and an integer. Set the integer initially to int.MinValue. As you iterate the list, if the current value is greater than your integer variable, append it to list 1. When this is not the case, clear list 1, but first copy list 1 to list 2 if it is longer than list 2. When you finish the sequence, return the longer list (and it's length).

You just need to break in down into a smaller problem, that of finding the length of an increasing sequence given a starting point.

In pseudo-code, that's something like:

```
def getSeqLen (int array[], int pos):
for i = pos + 1 to array.last_element:
if array[i] <= array[i-1]:
return i - pos
return array.last_element + 1 - pos
```

Then step through the array, looking at these individual sequences. You *know* that the sequences have to be separated at specific points since otherwise the sequences would be longer. In other words, there is no overlap of these increasing sequences:

```
def getLongestSeqLen (int array[]):
pos = 0
longlen = 0
while pos <= array.last_element:
len = getSeqLen (array, pos)
if len > longlen:
longlen = len
pos = pos + len
return longlen
```

By way of graphical explanation, consider the following sequence:

```
element#: 0 1 2 3 4 5 6 7 8 9 10 11 12
value: 9 10 12 7 8 9 6 5 6 7 8 7 8
^ ^ ^ ^ ^
```

In this case, the `^`

characters mark the unambiguous boundaries of a subsequence.

By starting at element 0, `getSeqLen`

returns 3. Since this is greater than the current longest length of 0, we save it and add 3 to the current position (to get 3).

Then at element 3, `getSeqLen`

returns 3. Since this is not greater than the current longest length of 3, we ignore it but we still add 3 to the current position (to get 6).

Then at element 6, `getSeqLen`

returns 1. Since this is not greater than the current longest length of 3, we ignore it but we still add 1 to the current position (to get 7).

Then at element 7, `getSeqLen`

returns 4. Since this is greater than the current longest length of 3, we save it and add 4 to the current position (to get 11).

Then at element 11, `getSeqLen`

returns 2. Since this is not greater than the current longest length of 4, we ignore it but we still add 2 to the current position (to get 13).

Then, since element 13 is beyond the end, we simply return the longest length found (4).

**As a performance tip too, if your current longest substring is longer than the remainder of the string, you can call it quits there!**

I have solved this in O(n log n) time here:

http://www.olhovsky.com/2009/11/extract-longest-increasing-sequence-from-any-sequence/

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)
```

Use the code like so:

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

Here is my solution:

```
public static int[] FindLongestSequence(int[] seq)
{
int c_min = 0, c_len = 1;
int min = 1, len = 0;
for (int i = 0; i < seq.Length - 1; i++)
{
if(seq[i] < seq[i+1])
{
c_len++;
if (c_len > len)
{
len = c_len;
min = c_min;
}
} else
{
c_min = i+1;
c_len = 1;
}
}
return seq.Skip(min).Take(len).ToArray();
}
}
```

One way to do it is with help from the Aggregate method:

```
var bestSubSequence = listOfInts.Skip(1).Aggregate(
Tuple.Create(int.MinValue, new List<int>(), new List<int>()),
(curr, next) =>
{
var bestList = curr.Item2.Count > curr.Item3.Count ? curr.Item2 : curr.Item3;
if (curr.Item1 > next)
return Tuple.Create(next, new List<int> {next}, bestList);
curr.Item2.Add(next);
return Tuple.Create(next, curr.Item2, bestList);
}).Item3;
```

It did not turn out as well as I had hoped when I started writing it and I think the other more direct ways to do it is better and easier to follow, but it might give a different perspective on how these kinds of tasks can be solved.

Similar Questions

Given a list say {a, b, c, d} Is there any easier way to generate list of sequential subsets like this (order of the result is not important) { {a}, {a b}, {a b c}, {a b c d}, {b},

Sorry for the mess that was here. I wanted a classic greedy algorithm for knapsack problem in haskell for integers. But there was other question - how to refer to list in list comprehension?

Can i use List or something?

If I add an event to my control in the markup, eg in and EntityDataSource add a OnUpdating, how can I find the method parameter list? eg how do I know to put in (object sender, EntityDataSourceChangi

I have a list: List<double> final=new List<double>(); final.Add(1); final.Add(2); final.Add(3); What sort of method could I use to find the mode of this list? Also, if there are two modes

I am using oracle 10g. My (simplified) table definition is CREATE TABLE Student (Rno INT PRIMARY KEY) ; Which contains the following rows | RNO | |-----| | 1 | | 2 | | 3 | | 6 | | 8 | | 9 | | 12 |

I'm trying to find the most pythonic way to find out if numbers in a list are sequential. To give some background, I have a list of numbers gathered that exist in a folder, and I need to find out whic

I have (or will have; its not written yet) a .NET web API controller method that I was just going to have return a list of ints as a JSON response. On the client side, I just wanted to deserialize the

I have a directory that contains sequentially numbered log files and some Excel spreadsheets used for analysis. The log file are ALWAYS sequentially numbered beginning at zero, but the number of them

I want the list of all functions executed to a certain point in code, somehow like debug_backtrace() but including functions not in the exact thread that leads to where debug_backtrace() is called. e.

Here is some code for a function I am writing that outputs whether a given date is valid or not: date = (input(Please enter a date (mm/dd/yyyy): )) monthStr, dayStr, yearStr = date.split(/) month

I know there is a simple function for this, but I can't find it anywhere. I have: a <- list(a=1,b=2) b <- list(c=3,d=4) c <- list(e=5,f=6) I want a list with 4 elements, list a, list b and t

What is the purpose of the sequential container adaptors (i.e; stack, queue) in C++? Thanks.

I am having problems with making a method that will return distinct integers of the array list. I really want to do it with removing the duplicates and then just display the array list. I cannot figur

How do I write a custom set of integers in Scala? Specifically I want a class with the following properties: It is immutable. It extends the Set trait. All collection operations return another object

How to multiply four 32-bit integers by another 4 integers? I didn't find any instruction which can do it.

I have to find all combinations using 3 integers without repetition in C++ application. I can calculate how many combination there are going to be when I specify how many integers do I have. unsigned

After looking on MSDN, it's still unclear to me how I should form a proper predicate to use the Find() method in List using a member variable of T (where T is a class) For example: public class Car {

How do I take the Cartesian join of two lists with integers in them? Can this be done with linq?

So I've read the theory, now trying to parse a file in Haskell - but am not getting anywhere. This is just so weird... Here is how my input file looks: m n k1, k2... a11, ...., an a21,.... a22 ... am

How can I create a vector S, with S[i] = 1, if Tv[i] is the closest number to an integer in I<- 6:10 S[i] = 0 else Tv <- c(5.946, 5.978, 6.01, 6.043, 6.075, 6.109, 6.14, 6.173, 6.205, 6.239, 6.

I want to make a script that does an insertion sort on the arguments provided by the user, like this: $ insertionSort 1 2 110 39 I expect it to return: [1 2 39 110] But it returns: [1 110 2 39]

Here's the situation. I have a sorted list of integers representing events that need to be fired at a certain millisecond. That list might look like: 0 1500 5000 9348 89234 109280 109281 109283 150000

I have 2 List of String variables: List<string> stringList1 List<string> stringList2 where stringList2 is a subset of stringList1 now I want all the elements on stringList1 that aren't in

Given this list of string values: 12345, 6789a, 9876, 23467b How do we use a Linq statement in C# to select only the integers? In other words, we only want to return 12345 and 9876.

OK, here's the scenario. I think it's pretty common, and I have solved it in a prior life using a brute-force approach, but I'm thinking there has to be a better way. Given an ordered list of names, a

I'm stuck on this SQL problem. I have a column that is a list of starting points (prevdoc), and anther column that lists how many sequential numbers I need after the starting point (exdiff). For examp

I'm creating a program that will open a file and search for a desired word within the text. I created the following word bank... Lawyer Smith Janes Doctor Michael Zane Teacher Maria Omaha #include <

Possible Duplicates: How to get difference between two dates in Year/Month/Week/Day? Difference in months between two dates (C#, .NET) Hi I'm a novice at c# and I need to find out the age of a vehic

I have some tagged files that i want to process. Each line in file has the following format (formatted for clarity): Name1 Tag1 Origin1 Name2 Tag2 Origin2 I need a C# solution that does the following

How do I find the playback time of media with gstreamer?

This question already has an answer here: python list of lists transpose without zip(*m) thing 4 answers Let's say I have a SINGLE list [[1,2,3],[4,5,6]] How do I transpose them so they will be

So I'm trying to use sequential search to check how many times a string comes up within my array. Within my program I ask the user to select which file they wish to open and be process. void search(c

How do I find a preexisting variable with a list of strings in Python? I have a list of strings, such as: letters = [C, A, M, P] and a set of preexisting variables, such as: C = pygame.image.

I have n records in my sequential file and i have to delete last 3 records in the sequential file by using COBOL program. How can I do this?

I was wondering how do I find out how many bytes does a character have?

Given the current node, how can I find its previous node in a Singly Linked List. Thanks. Logic will do , code is appreciated. We all know given a root node one can do a sequential traverse , I want t

I'm trying to write a basic program that spits out the English version of a number when the user inputs a numeral: input = 44 output = fourty four Is there a way to describe all integers? Basically I

how do I list subdirectories in windows using C++? Using code that would run cross-platorm is better.

If I have a class, how can I list all its instance variable names? eg: @interface MyClass : NSObject { int myInt; NSString* myString; NSMutableArray* myArray; } I would like to get myInt, myString

How can I use Watin to get the list of available button on a website? How do the watinTestRecorder do it?

how to find the size of a LINKED LIST (data structure) in c language?

In Python, how do you find the index of the first value greater than a threshold in a sorted list? I can think of several ways of doing this (linear search, hand-written dichotomy,..), but I'm looking

I'm trying to transform a function to make it execute in parallel instead of sequential in C#, but I'm not sure what I'm doing wrong: // sequential static void Romberg(double a, double b, int n, doubl

How can hdfs have a sequential block of 64MB when the underlying linux filesystem has only 4KB block sizes and a write of 64MB block can not be sequential. Any thoughts on this? I am not able to get a

I am trying to add Integers inside a list together with one line. The problem is that adding Integers in a string return an object itself and not the sum of the Integers. For example, I have the strin

I want to find out for how long (approximately) some block of code executes. Something like this: startStopwatch(); // do some calculations stopStopwatch(); printf(%lf, timeMesuredInSeconds); How?

I'm 15, and doing an assignment for school, I'm up to a part where i have to have the 'User' input a list of integers, the program must then add the integers in the list together and return: Total: $

I'd like to be able to get a char array of all the printable characters in C#, does anybody know how to do this? edit: By printable I mean the visible European characters, so yes, umlauts, tildes, acc

If I have the follow 2 sets of code, how do I glue them together? void c_function(void *ptr) { int i; for (i = 0; i < 10; i++) { printf(%p, ptr[i]); } return; } def python_routine(y): x = [] for