Loading...
RositsaDragoeva avatar RositsaDragoeva 2 Точки

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
kkaraivanov avatar kkaraivanov 486 Точки

Здравей! Пействам ти моето решение, мисля че ще ти помогне логиката. Опитах по условието да изграждам кода, но се обърках и започнах да следвам таблицата. Ето и решението ми.

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

namespace LongestIncreasingSubsequence
{
    class Program
    {
        public static void Main()
        {
            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));
        }
    }
}

 

0
DenisCholakov avatar DenisCholakov 2 Точки

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

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 235 Точки

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

Ивайло Кенов, 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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.