Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Longest Increasing Subsequence (LIS)
- Read a list of integers and find the longest increasing subsequence (LIS).
- If several such exist, print the leftmost.
- • 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 calculate shall len[p] for p = 0 … n-1 as follows:
- o Let left is the leftmost position on the left of p (left < p), such that len[left] is the maximal possible.
- o Then, len[p] = 1 + len[left]. If left does not exist, len[p] = 1.
- o 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].
- */
- using System;
- using System.Collections.Generic;
- using System.Linq;
- internal static class LongestIncreasingSubsequence
- {
- private static void Main()
- {
- var numbers = Console.ReadLine().Split()
- .Select(int.Parse)
- .ToArray();
- var maxLen = 0;
- var lastIndex = -1;
- var len = new int[numbers.Length];
- var prev = new int[numbers.Length];
- for (int i = 0; i < numbers.Length; i++)
- {
- len[i] = 1;
- prev[i] = -1;
- for (int j = 0; j < i; j++)
- {
- if (numbers[j] < numbers[i] && len[j] + 1 > len[i])
- {
- len[i] = len[j] + 1;
- prev[i] = j;
- }
- }
- if (len[i] > maxLen)
- {
- maxLen = len[i];
- lastIndex = i;
- }
- }
- var longestSeq = new Stack<int>();
- while (lastIndex > -1)
- {
- longestSeq.Push(numbers[lastIndex]);
- lastIndex = prev[lastIndex];
- }
- Console.WriteLine(string.Join(" ", longestSeq));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement