How do I find sequential integers in a list in C#?

How do I find the longest increasing sub-sequence of integers from a list of 开发者_运维知识库integers in C#?

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

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

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();
    }
}

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

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)

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.