Longest Increasing Subsequence (using Dynamic Programing)

/*
Longest Increasing Subsequence (LIS)
Read a list of integers and find the longest increasing subsequence (LIS).
If several such exist, print the leftmost.
• Assume we have n numbers in an array nums[0…n-1].
• Let len[p] holds the length of the longest increasing subsequence (LIS) ending at position p.
• In a for loop, we calculate shall len[p] for p = 0 … n-1 as follows:
    o   Let left is the leftmost position on the left of p (left < p), such that len[left] is the maximal possible.
    o   Then, len[p] = 1 + len[left]. If left does not exist, len[p] = 1.
    o   Also save prev[p] = left (we hold if prev[] the previous position, used to obtain the best length for position p).
• Once the values for len[0…n-1] are calculated, restore the LIS starting from position p such that len[p] is maximal
    and go back and back through p = prev[p].
*/

    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static class LongestIncreasingSubsequence
    {
        private static void Main()
        {
            var numbers = Console.ReadLine().Split()
                .Select(int.Parse)
                .ToArray();

            var maxLen = 0;
            var lastIndex = -1;
            var len = new int[numbers.Length];
            var prev = new int[numbers.Length];
            for (int i = 0; i < numbers.Length; i++)
            {
                len[i] = 1;
                prev[i] = -1;
                for (int j = 0; j < i; j++)
                {
                    if (numbers[j] < numbers[i] && len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        prev[i] = j;
                    }
                }

                if (len[i] > maxLen)
                {
                    maxLen = len[i];
                    lastIndex = i;
                }
            }

            var longestSeq = new Stack<int>();
            while (lastIndex > -1)
            {
                longestSeq.Push(numbers[lastIndex]);
                lastIndex = prev[lastIndex];
            }

            Console.WriteLine(string.Join(" ", longestSeq));
        }
    }