15. Longest Increasing Subsequence (LIS)

15. Longest Increasing Subsequence (LIS)
Read a list of integers and find the longest increasing subsequence (LIS). If several such exist, print the leftmost.
Examples
Input	                                     Output
1	                                         1
7 3 5 8 -1 0 6 7	                         3 5 6 7
1 2 5 3 5 2 4 1	                             1 2 3 5
0 10 20 30 30 40 1 50 2 3 4 5 6	             0 1 2 3 4 5 6
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8	         3 4 5 6 7 8 16
3 14 5 12 15 7 8 9 11 10 1	                 3 5 7 8 9 11
Hints
•	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 shall calculate 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 largest 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].
•	The table below illustrates these computations:
index	0	  1      2	      3	          4	         5	     6	         7	         8	             9	            10
nums[]	3	  14     5	     12	         15	         7	     8	         9	        11	            10	             1
len[]	1	  2      2	      3	          4	         3	     4	         5	         6	             6	             1
prev[] -1	  0      0	      2	          3	         2	     5	         6	         7	             7	            -1
LIS	    {3}	{3,14}	{3,5}	{3,5,12}	{3,5,12,15}	{3,5,7}	{3,5,7,8}	{3,5,7,8,9}	{3,5,7,8,9,11}	{3,5,7,8,9,10}	{1}


using System;
using System.Linq;

namespace _05LongestIncreasingSubsequence_LIS_
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] sequence = Console.ReadLine()
                 .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
                 .Select(x => int.Parse(x))
                 .ToArray();

            int[] lis;
            int[] len = new int[sequence.Length];
            int[] prev = new int[sequence.Length];
            int maxLength = 0;
            int lastIndex = -1;

            // обхождам поредицата
            for (int i = 0; i < sequence.Length; i++)
            {
                // len && prev съответно = 1 && -1
                len[i] = 1;
                prev[i] = -1;

                // обхождам поредицата и сравнявам за най-добра дължина на поредица
                // if i == j -> цикъл j няма да се изпълни
                for (int j = 0; j < i; j++)
                {
                    // ако текущата стойност j/в ляво/ е по-малка от i/в дясно/
                    // && текущия брой елементи j >= броя елементи на i -> броя на елементите /поредицата/ ще нараства
                    if (sequence[j] < sequence[i] && len[j] >= len[i])
                    {
                        len[i] = 1 + len[j];
                        prev[i] = j; // запазваме индекса на най добрия елемент от поредицата
                    }
                }
                // запазвам максималния брой елементи
                if (len[i] > maxLength)
                {
                    maxLength = len[i];
                    lastIndex = i;
                }
            }
            lis = new int[maxLength];
            for (int i = 0; i < maxLength; i++)
            {
                lis[i] = sequence[lastIndex];
                lastIndex = prev[lastIndex];
            }
            Array.Reverse(lis);
            Console.WriteLine(string.Join(" ", lis));
        }
    }
}