mirror of
https://github.com/TheAlgorithms/Python.git
synced 2025-01-18 00:07:00 +00:00
f04d308431
* Create longest_increasing_subsequence_iterative.py * Update longest_increasing_subsequence_iterative.py * Update longest_increasing_subsequence_iterative.py --------- Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
73 lines
2.1 KiB
Python
73 lines
2.1 KiB
Python
"""
|
|
Author : Sanjay Muthu <https://github.com/XenoBytesX>
|
|
|
|
This is a pure Python implementation of Dynamic Programming solution to the longest
|
|
increasing subsequence of a given sequence.
|
|
|
|
The problem is:
|
|
Given an array, to find the longest and increasing sub-array in that given array and
|
|
return it.
|
|
|
|
Example:
|
|
``[10, 22, 9, 33, 21, 50, 41, 60, 80]`` as input will return
|
|
``[10, 22, 33, 50, 60, 80]`` as output
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
import copy
|
|
|
|
|
|
def longest_subsequence(array: list[int]) -> list[int]:
|
|
"""
|
|
Some examples
|
|
|
|
>>> longest_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])
|
|
[10, 22, 33, 50, 60, 80]
|
|
>>> longest_subsequence([4, 8, 7, 5, 1, 12, 2, 3, 9])
|
|
[1, 2, 3, 9]
|
|
>>> longest_subsequence([9, 8, 7, 6, 5, 7])
|
|
[7, 7]
|
|
>>> longest_subsequence([28, 26, 12, 23, 35, 39])
|
|
[12, 23, 35, 39]
|
|
>>> longest_subsequence([1, 1, 1])
|
|
[1, 1, 1]
|
|
>>> longest_subsequence([])
|
|
[]
|
|
"""
|
|
n = len(array)
|
|
# The longest increasing subsequence ending at array[i]
|
|
longest_increasing_subsequence = []
|
|
for i in range(n):
|
|
longest_increasing_subsequence.append([array[i]])
|
|
|
|
for i in range(1, n):
|
|
for prev in range(i):
|
|
# If array[prev] is less than or equal to array[i], then
|
|
# longest_increasing_subsequence[prev] + array[i]
|
|
# is a valid increasing subsequence
|
|
|
|
# longest_increasing_subsequence[i] is only set to
|
|
# longest_increasing_subsequence[prev] + array[i] if the length is longer.
|
|
|
|
if array[prev] <= array[i] and len(
|
|
longest_increasing_subsequence[prev]
|
|
) + 1 > len(longest_increasing_subsequence[i]):
|
|
longest_increasing_subsequence[i] = copy.copy(
|
|
longest_increasing_subsequence[prev]
|
|
)
|
|
longest_increasing_subsequence[i].append(array[i])
|
|
|
|
result: list[int] = []
|
|
for i in range(n):
|
|
if len(longest_increasing_subsequence[i]) > len(result):
|
|
result = longest_increasing_subsequence[i]
|
|
|
|
return result
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod()
|