Fix dynamic_programming/longest_increasing_subsequence.py

[MaximSmolskiy]

Repository commit

bae33ac

Python version (python --version)

Python 3.8.10

Dependencies version (pip freeze)

absl-py==1.3.0
alabaster==0.7.12
alembic==1.8.1
apturl==0.5.2
astroid==3.2.4
async-timeout==4.0.2
attrs==22.1.0
autoapi==2.0.1
Babel==2.11.0
bcrypt==3.1.7
beautifulsoup4==4.11.1
bidict==0.22.0
black==21.9b0
blinker==1.4
bottle==0.12.18
Brlapi==0.7.0
cachetools==5.2.0
certifi==2019.11.28
cfgv==3.3.1
chardet==3.0.4
charset-normalizer==2.1.1
click==8.0.1
cloudpickle==2.2.0
cmake==3.24.3
cmake-format==0.6.13
cmakelang==0.6.13
colorama==0.4.5
commentjson==0.9.0
conan==1.28.1
cryptography==2.8
cupshelpers==1.0
cvxpy==1.2.2
cycler==0.11.0
Cython==0.29.32
databricks-cli==0.17.3
dataclasses==0.6
dbus-python==1.2.16
decorator==4.4.2
defer==1.0.6
Deprecated==1.2.13
deprecation==2.0.7
dill==0.3.6
distlib==0.3.6
distro==1.1.0
distro-info==0.23+ubuntu1.1
docker==6.0.1
docopt==0.6.2
docutils==0.20.1
dom_toml==2.0.0
domdf-python-tools==3.9.0
dotmap==1.3.30
duplicity==0.8.12.0
ecos==2.0.10
entrypoints==0.3
exceptiongroup==1.0.1
fasteners==0.18
filelock==3.8.0
fire==0.4.0
flake8==5.0.4
Flask==2.2.2
fonttools==4.30.0
future==0.18.2
GDAL==3.0.4
gdown==4.5.1
geojson==2.5.0
gitdb==4.0.9
GitPython==3.1.29
google-auth==2.14.1
google-auth-oauthlib==0.4.6
GPUtil==1.4.0
greenlet==2.0.1
grpcio==1.50.0
gunicorn==20.1.0
gym==0.26.2
gym-notices==0.0.8
h5py==3.7.0
html5lib==1.0.1
httplib2==0.14.0
hyperopt==0.1.2
identify==2.5.12
idna==2.8
imageio==2.16.2
imagesize==1.4.1
importlib-metadata==5.0.0
importlib-resources==5.10.0
iniconfig==1.1.1
intel-openmp==2022.1.0
ipython_genutils==0.2.0
isort==5.10.1
iteration_utilities==0.12.1
itsdangerous==2.1.2
Jinja2==3.0.3
joblib==1.1.0
jplephem==2.18
jsonpickle==1.5.2
jsonschema==3.2.0
jupyter-core==4.6.3
keyring==18.0.1
kiwisolver==1.3.2
language-selector==0.1
lark-parser==0.7.8
laspy==2.1.2
launchpadlib==1.10.13
lazr.restfulclient==0.14.2
lazr.uri==1.0.3
lightgbm==3.3.3
line-profiler==4.0.3
llvmlite==0.37.0
lockfile==0.12.2
loguru==0.6.0
louis==3.12.0
lxml==4.5.0
macaroonbakery==1.3.1
Mako==1.2.3
Markdown==3.4.1
markdown-it-py==2.1.0
MarkupSafe==2.1.1
matplotlib==3.5.1
mccabe==0.7.0
mdit-py-plugins==0.3.3
mdurl==0.1.2
mkl==2022.1.0
mlflow==1.30.0
monotonic==1.5
more-itertools==4.2.0
mpmath==1.2.1
munch==2.5.0
mypy==1.0.1
mypy-extensions==0.4.3
myst-parser==0.18.1
natsort==8.4.0
nbformat==5.0.4
networkx==2.7.1
node-semver==0.6.1
nodeenv==1.7.0
numba==0.54.0
numexpr==2.8.4
numpy==1.20.3
numpy-quaternion==2021.8.30.10.33.11
oauthlib==3.1.0
olefile==0.46
opencv-contrib-python==4.6.0.66
opencv-python==4.5.5.62
osqp==0.6.2.post5
OWSLib==0.19.1
packaging==21.3
pandas==1.5.1
paramiko==2.6.0
patch-ng==1.17.4
pathspec==0.9.0
patsy==0.5.3
pexpect==4.6.0
Pillow==9.1.0
pip==22.3.1
pipdeptree==2.16.1
platformdirs==2.4.0
plotly==5.11.0
pluggy==1.0.0
pluginbase==1.0.0
plyfile==0.7.4
pre-commit==2.21.0
prometheus-client==0.15.0
prometheus-flask-exporter==0.21.0
psutil==5.9.3
psycopg2==2.8.4
py-cpuinfo==9.0.0
pyasn1==0.4.8
pyasn1-modules==0.2.8
pybind11==2.7.1
pycairo==1.16.2
pycodestyle==2.9.1
pycups==1.9.73
pydensecrf==1.0rc2
pydot==1.4.1
pydot-ng==2.0.0
pydotplus==2.0.2
PyExifTool==0.5.4
pyflakes==2.5.0
Pygments==2.13.0
pygmo==2.15.0
pygmo-plugins-nonfree==0.21
PyGObject==3.36.0
PyJWT==1.7.1
pykep==2.6

Editable install with no version control (pylogic==0.0.0)

-e /home/maxim/Загрузки/py-logic
pymacaroons==0.13.0
pymap3d==3.0.1
pymongo==3.7.2
PyNaCl==1.3.0
pyparsing==2.4.7
pyproj==3.3.1
pyqlib @ file:///home/maxim/%D0%97%D0%B0%D0%B3%D1%80%D1%83%D0%B7%D0%BA%D0%B8/qlib
PyQt5==5.14.1
pyquaternion==0.9.9
pyRFC3339==1.1
pyrsistent==0.15.5
pyshp==2.3.1
PySocks==1.7.1
pytest==7.2.0
python-apt==2.0.1+ubuntu0.20.4.1
python-dateutil==2.8.2
python-debian==0.1.36+ubuntu1.1
python-engineio==4.3.4
python-redis-lock==4.0.0
python-socketio==5.7.2
pytz==2022.6
PyWavelets==1.4.1
pyxdg==0.26
PyYAML==5.3.1
qdldl==0.1.5.post2
Quaternion==3.5.2.post4
quaternionic==0.4.1
querystring-parser==1.2.4
redis==4.3.4
regex==2021.9.30
reportlab==3.5.34
requests==2.28.1
requests-oauthlib==1.3.1
requests-unixsocket==0.2.0
retrying==1.3.3
roman==2.0.0
rsa==4.9
ruamel.yaml==0.17.21
ruamel.yaml.clib==0.2.7
ruff==0.2.0
sacred==0.8.2
schedule==1.1.0
scikit-image==0.19.3
scikit-learn==1.1.2
scikit-spatial==6.7.0
scipy==1.7.1
screen-resolution-extra==0.0.0
scs==3.2.2
SecretStorage==2.3.1
setuptools==45.2.0
sgp4==2.21
simplejson==3.16.0
sip==4.19.21
six==1.14.0
sklearn==0.0
skyfield==1.45
smmap==5.0.0
snowballstemmer==2.2.0
soupsieve==2.3.2.post1
Sphinx==7.1.2
sphinx-autoapi==3.4.0
sphinx-pyproject==0.3.0
sphinx-rtd-theme==2.0.0
sphinxcontrib-applehelp==1.0.2
sphinxcontrib-devhelp==1.0.2
sphinxcontrib-htmlhelp==2.0.0
sphinxcontrib-jquery==4.1
sphinxcontrib-jsmath==1.0.1
sphinxcontrib-qthelp==1.0.3
sphinxcontrib-serializinghtml==1.1.5
SQLAlchemy==1.4.43
sqlparse==0.4.3
statsmodels==0.13.5
stdlib-list==0.10.0
sympy==1.8
system-service==0.3
systemd-python==234
tables==3.7.0
tabulate==0.9.0
tbb==2021.6.0
tenacity==8.1.0
tensorboard==2.11.0
tensorboard-data-server==0.6.1
tensorboard-plugin-wit==1.8.1
termcolor==2.1.0
threadpoolctl==3.1.0
tianshou==0.4.10
tifffile==2022.10.10
toml==0.10.2
tomli==2.2.1
torch==1.11.0+cu113
torchaudio==0.11.0+cu113
torchvision==0.12.0+cu113
tornado==6.2
tqdm==4.62.3
traitlets==4.3.3
typing_extensions==4.12.2
ubuntu-drivers-common==0.0.0
ubuntu-pro-client==8001
unattended-upgrades==0.1
urllib3==1.26.12
usb-creator==0.3.7
virtualenv==20.17.1
wadllib==1.3.3
webencodings==0.5.1
websocket-client==1.4.2
Werkzeug==2.2.2
wheel==0.34.2
wrapt==1.14.1
xkit==0.0.0
xlrd==2.0.1
yadisk==1.2.15
yapf==0.31.0
zipp==3.10.0
absl-py==1.3.0
alabaster==0.7.12
alembic==1.8.1
apturl==0.5.2
astroid==3.2.4
async-timeout==4.0.2
attrs==22.1.0
autoapi==2.0.1
Babel==2.11.0
bcrypt==3.1.7
beautifulsoup4==4.11.1
bidict==0.22.0
black==21.9b0
blinker==1.4
bottle==0.12.18
Brlapi==0.7.0
cachetools==5.2.0
certifi==2019.11.28
cfgv==3.3.1
chardet==3.0.4
charset-normalizer==2.1.1
click==8.0.1
cloudpickle==2.2.0
cmake==3.24.3
cmake-format==0.6.13
cmakelang==0.6.13
colorama==0.4.5
commentjson==0.9.0
conan==1.28.1
cryptography==2.8
cupshelpers==1.0
cvxpy==1.2.2
cycler==0.11.0
Cython==0.29.32
databricks-cli==0.17.3
dataclasses==0.6
dbus-python==1.2.16
decorator==4.4.2
defer==1.0.6
Deprecated==1.2.13
deprecation==2.0.7
dill==0.3.6
distlib==0.3.6
distro==1.1.0
distro-info==0.23+ubuntu1.1
docker==6.0.1
docopt==0.6.2
docutils==0.20.1
dom_toml==2.0.0
domdf-python-tools==3.9.0
dotmap==1.3.30
duplicity==0.8.12.0
ecos==2.0.10
entrypoints==0.3
exceptiongroup==1.0.1
fasteners==0.18
filelock==3.8.0
fire==0.4.0
flake8==5.0.4
Flask==2.2.2
fonttools==4.30.0
future==0.18.2
GDAL==3.0.4
gdown==4.5.1
geojson==2.5.0
gitdb==4.0.9
GitPython==3.1.29
google-auth==2.14.1
google-auth-oauthlib==0.4.6
GPUtil==1.4.0
greenlet==2.0.1
grpcio==1.50.0
gunicorn==20.1.0
gym==0.26.2
gym-notices==0.0.8
h5py==3.7.0
html5lib==1.0.1
httplib2==0.14.0
hyperopt==0.1.2
identify==2.5.12
idna==2.8
imageio==2.16.2
imagesize==1.4.1
importlib-metadata==5.0.0
importlib-resources==5.10.0
iniconfig==1.1.1
intel-openmp==2022.1.0
ipython_genutils==0.2.0
isort==5.10.1
iteration_utilities==0.12.1
itsdangerous==2.1.2
Jinja2==3.0.3
joblib==1.1.0
jplephem==2.18
jsonpickle==1.5.2
jsonschema==3.2.0
jupyter-core==4.6.3
keyring==18.0.1
kiwisolver==1.3.2
language-selector==0.1
lark-parser==0.7.8
laspy==2.1.2
launchpadlib==1.10.13
lazr.restfulclient==0.14.2
lazr.uri==1.0.3
lightgbm==3.3.3
line-profiler==4.0.3
llvmlite==0.37.0
lockfile==0.12.2
loguru==0.6.0
louis==3.12.0
lxml==4.5.0
macaroonbakery==1.3.1
Mako==1.2.3
Markdown==3.4.1
markdown-it-py==2.1.0
MarkupSafe==2.1.1
matplotlib==3.5.1
mccabe==0.7.0
mdit-py-plugins==0.3.3
mdurl==0.1.2
mkl==2022.1.0
mlflow==1.30.0
monotonic==1.5
more-itertools==4.2.0
mpmath==1.2.1
munch==2.5.0
mypy==1.0.1
mypy-extensions==0.4.3
myst-parser==0.18.1
natsort==8.4.0
nbformat==5.0.4
networkx==2.7.1
node-semver==0.6.1
nodeenv==1.7.0
numba==0.54.0
numexpr==2.8.4
numpy==1.20.3
numpy-quaternion==2021.8.30.10.33.11
oauthlib==3.1.0
olefile==0.46
opencv-contrib-python==4.6.0.66
opencv-python==4.5.5.62
osqp==0.6.2.post5
OWSLib==0.19.1
packaging==21.3
pandas==1.5.1
paramiko==2.6.0
patch-ng==1.17.4
pathspec==0.9.0
patsy==0.5.3
pexpect==4.6.0
Pillow==9.1.0
pip==22.3.1
pipdeptree==2.16.1
platformdirs==2.4.0
plotly==5.11.0
pluggy==1.0.0
pluginbase==1.0.0
plyfile==0.7.4
pre-commit==2.21.0
prometheus-client==0.15.0
prometheus-flask-exporter==0.21.0
psutil==5.9.3
psycopg2==2.8.4
py-cpuinfo==9.0.0
pyasn1==0.4.8
pyasn1-modules==0.2.8
pybind11==2.7.1
pycairo==1.16.2
pycodestyle==2.9.1
pycups==1.9.73
pydensecrf==1.0rc2
pydot==1.4.1
pydot-ng==2.0.0
pydotplus==2.0.2
PyExifTool==0.5.4
pyflakes==2.5.0
Pygments==2.13.0
pygmo==2.15.0
pygmo-plugins-nonfree==0.21
PyGObject==3.36.0
PyJWT==1.7.1
pykep==2.6

Editable install with no version control (pylogic==0.0.0)

-e /home/maxim/Загрузки/py-logic
pymacaroons==0.13.0
pymap3d==3.0.1
pymongo==3.7.2
PyNaCl==1.3.0
pyparsing==2.4.7
pyproj==3.3.1
pyqlib @ file:///home/maxim/%D0%97%D0%B0%D0%B3%D1%80%D1%83%D0%B7%D0%BA%D0%B8/qlib
PyQt5==5.14.1
pyquaternion==0.9.9
pyRFC3339==1.1
pyrsistent==0.15.5
pyshp==2.3.1
PySocks==1.7.1
pytest==7.2.0
python-apt==2.0.1+ubuntu0.20.4.1
python-dateutil==2.8.2
python-debian==0.1.36+ubuntu1.1
python-engineio==4.3.4
python-redis-lock==4.0.0
python-socketio==5.7.2
pytz==2022.6
PyWavelets==1.4.1
pyxdg==0.26
PyYAML==5.3.1
qdldl==0.1.5.post2
Quaternion==3.5.2.post4
quaternionic==0.4.1
querystring-parser==1.2.4
redis==4.3.4
regex==2021.9.30
reportlab==3.5.34
requests==2.28.1
requests-oauthlib==1.3.1
requests-unixsocket==0.2.0
retrying==1.3.3
roman==2.0.0
rsa==4.9
ruamel.yaml==0.17.21
ruamel.yaml.clib==0.2.7
ruff==0.2.0
sacred==0.8.2
schedule==1.1.0
scikit-image==0.19.3
scikit-learn==1.1.2
scikit-spatial==6.7.0
scipy==1.7.1
screen-resolution-extra==0.0.0
scs==3.2.2
SecretStorage==2.3.1
setuptools==45.2.0
sgp4==2.21
simplejson==3.16.0
sip==4.19.21
six==1.14.0
sklearn==0.0
skyfield==1.45
smmap==5.0.0
snowballstemmer==2.2.0
soupsieve==2.3.2.post1
Sphinx==7.1.2
sphinx-autoapi==3.4.0
sphinx-pyproject==0.3.0
sphinx-rtd-theme==2.0.0
sphinxcontrib-applehelp==1.0.2
sphinxcontrib-devhelp==1.0.2
sphinxcontrib-htmlhelp==2.0.0
sphinxcontrib-jquery==4.1
sphinxcontrib-jsmath==1.0.1
sphinxcontrib-qthelp==1.0.3
sphinxcontrib-serializinghtml==1.1.5
SQLAlchemy==1.4.43
sqlparse==0.4.3
statsmodels==0.13.5
stdlib-list==0.10.0
sympy==1.8
system-service==0.3
systemd-python==234
tables==3.7.0
tabulate==0.9.0
tbb==2021.6.0
tenacity==8.1.0
tensorboard==2.11.0
tensorboard-data-server==0.6.1
tensorboard-plugin-wit==1.8.1
termcolor==2.1.0
threadpoolctl==3.1.0
tianshou==0.4.10
tifffile==2022.10.10
toml==0.10.2
tomli==2.2.1
torch==1.11.0+cu113
torchaudio==0.11.0+cu113
torchvision==0.12.0+cu113
tornado==6.2
tqdm==4.62.3
traitlets==4.3.3
typing_extensions==4.12.2
ubuntu-drivers-common==0.0.0
ubuntu-pro-client==8001
unattended-upgrades==0.1
urllib3==1.26.12
usb-creator==0.3.7
virtualenv==20.17.1
wadllib==1.3.3
webencodings==0.5.1
websocket-client==1.4.2
Werkzeug==2.2.2
wheel==0.34.2
wrapt==1.14.1
xkit==0.0.0
xlrd==2.0.1
yadisk==1.2.15
yapf==0.31.0
zipp==3.10.0

Expected behavior

>>> longest_subsequence([28, 26, 12, 23, 35, 39])
[12, 23, 35, 39]

>>> longest_subsequence([9, 8, 7, 6, 5, 7])
[7, 7] or [6, 7] or [5, 7]

Actual behavior

#12499

>>> longest_subsequence([28, 26, 12, 23, 35, 39])
[26, 35, 39]

>>> longest_subsequence([9, 8, 7, 6, 5, 7])
[8]