## Arrays - More Exercise - 05. Longest Increasing Subsequence

Здравейте,

направих две странни решения на тази задача с използването на речник,

обаче го докарвам до 50/50. Хинтовете ме объркваха и не съм се водила много

по тях. Струва ми се, че може да се завърши някак този код, примерно като комбинация

между двата кода.  Ще съм благодарна ако някой помогне!

## 1.  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:
• Let left is the leftmost position on the left of p (left < p), such that len[left] is the largest possible.
• Then, len[p] = 1 + len[left]. If left does not exist, len[p] = 1.
• 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}

Ето код № 1:

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

namespace LIS4
{
class Program
{
static void Main(string[] args)
{
.Split(" ")
.Select(int.Parse)
.ToList();

var list = new Dictionary<int, List<int>>();
var seq = new List<int> { nums[0] };
var bestSeq = seq;

for (int i = 1; i < nums.Count; i++)
{
var newSeq = new List<int>();

if (nums[i] <= newSeq[newSeq.Count - 1])
{
if (nums[i] < newSeq[newSeq.Count - 1])
{
for (int j = newSeq.Count - 1; j >= 0; j--)
{
if (nums[i] < newSeq[j])
{
newSeq.RemoveAt(j);
if (newSeq.Count == 0)
{
break;
}
}
if (nums[i] == newSeq[newSeq.Count - 1])
{
newSeq.RemoveAt(newSeq.Count - 1);
break;
}
}
}
}
else
{
}

if (newSeq.Count > bestSeq.Count)
{
bestSeq = newSeq;
}
}

var longestSeq = new List<int> { 1 };

foreach (var item in list)
{
if (item.Value.Count > longestSeq.Count)
{
longestSeq = item.Value;
}
}
Console.WriteLine(string.Join(" ", longestSeq));
}
}
}

Ето и код № 2:

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

namespace LIS1
{
class Program
{
static void Main(string[] args)
{
.Split(" ")
.Select(int.Parse)
.ToList();

var list = new Dictionary<int, List<int>>();
var seq = new List<int> { nums[0] };
int longest = seq.Count;
var longestSeq = new List<int>();

for (int i = 1; i < nums.Count; i++)
{
var newSeq = new List<int> { nums[i] };
var temp = new List<int> { nums[i] };

for (int j = 0; j < list.Count; j++)
{
temp = new List<int> { nums[i] };

if (list[j][0] < newSeq[0] && list[j][list[j].Count - 1] < newSeq[0])
{
temp.InsertRange(0, list[j]);

if (temp.Count >= longest)
{
if (temp.Count > longest)
{
longest = temp.Count;
longestSeq = temp;
}
if (temp.Count == longest)
{
if (temp[temp.Count - 1] < longestSeq[longestSeq.Count - 1])
{
longestSeq = temp;
}
else
{
temp = longestSeq;
}
}
}
}
else
{
continue;
}
}
}

var theLongestSeq = new List<int> { 1 };

foreach (var item in list)
{
if (item.Value.Count > theLongestSeq.Count)
{
theLongestSeq = item.Value;
}
}
Console.WriteLine(string.Join(" ", theLongestSeq));
}
}
}