Здравейте,

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

обаче го докарвам до 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)
        {
            var nums = Console.ReadLine()
                              .Split(" ")
                              .Select(int.Parse)
                              .ToList();

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

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

                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;
                            }
                        }
                        newSeq.Add(nums[i]);
                    }
                }
                else
                {
                    newSeq.Add(nums[i]);
                }

                list.Add(0 + i, newSeq);

                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)
        {
            var nums = Console.ReadLine()
                              .Split(" ")
                              .Select(int.Parse)
                              .ToList();

            var list = new Dictionary<int, List<int>>();
            var seq = new List<int> { nums[0] };
            list.Add(0, seq);
            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;
                    }
                }
                list.Add(0 + i, temp);
            }

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