Longest Inc Subseq

AlgorithmAlgorithmBeginner
Practice Now

This tutorial is from open-source community. Access the source code

Introduction

In computer science, the Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. This subsequence is not necessarily contiguous, or unique.


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) algorithm/BasicAlgorithmsGroup -.-> algorithm/sorting_searching("`Sorting Searching`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills algorithm/sorting_searching -.-> lab-268863{{"`Longest Inc Subseq`"}} python/conditional_statements -.-> lab-268863{{"`Longest Inc Subseq`"}} python/for_loops -.-> lab-268863{{"`Longest Inc Subseq`"}} python/while_loops -.-> lab-268863{{"`Longest Inc Subseq`"}} python/lists -.-> lab-268863{{"`Longest Inc Subseq`"}} python/tuples -.-> lab-268863{{"`Longest Inc Subseq`"}} python/function_definition -.-> lab-268863{{"`Longest Inc Subseq`"}} python/classes_objects -.-> lab-268863{{"`Longest Inc Subseq`"}} python/encapsulation -.-> lab-268863{{"`Longest Inc Subseq`"}} python/raising_exceptions -.-> lab-268863{{"`Longest Inc Subseq`"}} python/build_in_functions -.-> lab-268863{{"`Longest Inc Subseq`"}} end

Longest Increasing Subsequence

Problem

Given a sequence of integers, find the longest increasing subsequence. The subsequence can be non-contiguous and may contain duplicates. If there are multiple solutions, return any one.

Requirements

To solve this problem, we need to consider the following requirements:

  • Are duplicates possible?
    • Yes
  • Can we assume the inputs are integers?
    • Yes
  • Can we assume the inputs are valid?
    • No, we need to handle invalid inputs.
  • Do we expect the result to be an array of the longest increasing subsequence?
    • Yes
  • Can we assume this fits memory?
    • Yes

Example Usage

Here are some examples of how this function can be used:

  • None -> Exception
  • [] -> []
  • [3, 4, -1, 0, 6, 2, 3] -> [-1, 0, 2, 3]

Summary

In summary, the Longest Increasing Subsequence problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. We can solve this problem by considering the requirements mentioned above.

Other Algorithm Tutorials you may like