Професионална програма
Loading...
RositsaDragoeva avatar RositsaDragoeva 0 Точки

More Exercises: Arrays - 5. Longest Increasing Subsequence (LIS)

Здравейте,

Дайте идея за решение на задачата. Или поне каква логика трябва да се следва. Ако може с материала, който сме взели до сега - Масиви. Все пак е в задачите за масиви.

Аз съм я направила и дава 100/100, но не ми допада.. искам да я оптимизирам, тъй като моя вариянт не дава правилно решение на всички случаи, а това в judje е късмет, мисля аз :) .

Благодаря.

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}

Тагове:
0
Module: C# Advanced 01/02/2020 09:37:08
DenisCholakov avatar DenisCholakov 1 Точки

Това съм направил аз 

using System;
using System.ComponentModel.DataAnnotations;
using System.Linq;
using System.Runtime.InteropServices;

namespace LargestSeq
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int[] index = new int[nums.Length];

            int maxIndex = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[j] < nums[i] && index[j] > index[i] - 1)
                    {
                        index[i] = index[j] + 1;
                        if (index[i] > index[maxIndex])
                        {
                            maxIndex = i;
                        }
                    }
                }
            }

            Print(maxIndex, nums, index);
        }

        static void Print(int maxIndex, int[] nums, int[] index)
        {
            bool isFirst = true;
            for (int i = 0; i < maxIndex; i++)
            {
                if (nums[i] < nums[maxIndex] && index[i] == index[maxIndex] - 1 && isFirst)
                {
                    isFirst = false;
                    Print(i, nums, index);
                }
            }

            Console.Write(nums[maxIndex] + " ");
        }
    }
}

0
Elena123456 avatar Elena123456 64 Точки

Бих искала да помоля някой, ако има свободно време и желание разбира се, да ми покаже как да взема самите елементи от най-дългата нарастваща поредица. Аз имам направен алгоритъма за големината на най-дългата нарастваща поредица, но се затруднявам да й изпечатам елементите. Доколкото разбрах трябва да направя още един масив, в който да пазя индексите на най-дългата предишна поредица.

Ивайло Кенов, 45 мин видео само за тази задача- https://softuni.bg/trainings/resources/video/42262/video-8-august-2019-ivaylo-kenov-longest-increasing-subsequence-algorithms-july-2019-online/2459

 

using System;
using System.Linq;

namespace LongestIncreasingSubsequence
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int[] sequence = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] len = new int[sequence.Length];
            int maxLength = 0;

            for (int currentI = 0; currentI < sequence.Length; currentI++)
            {
                len[currentI] = 1;

                for (int prevI = 0; prevI <= currentI - 1; prevI++)
                {
                    if (sequence[currentI] > sequence[prevI] && len[prevI] >= len[currentI])
                    {

                        len[currentI] = len[prevI] + 1;
                    }
                }

                if (len[currentI] > maxLength)
                {
                    maxLength = len[currentI];
                }
            }
            Console.WriteLine(maxLength);

        }
    }
}



 

0
18/09/2020 21:11:47