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} |
DenisCholakov U genious!!!
Бих искала да помоля някой, ако има свободно време и желание разбира се, да ми покаже как да взема самите елементи от най-дългата нарастваща поредица. Аз имам направен алгоритъма за големината на най-дългата нарастваща поредица, но се затруднявам да й изпечатам елементите. Доколкото разбрах трябва да направя още един масив, в който да пазя индексите на най-дългата предишна поредица.
Ивайло Кенов, 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);
}
}
}