Now at this point you have become an algorithm expert and it’s the right time to increase the difficulty level. You have given an array M = {1 ,2, 3, 8, 6, 7, 9, 10, 2, 1}. You have to calculate the longest increasing with decreasing subsequence in the array.
Now at this point you have become an
difficulty level. You have given an array M = {1 ,2, 3, 8, 6, 7, 9, 10, 2, 1}. You have to calculate the
longest increasing with decreasing subsequence in the array. Let’s understand what a subsequence
is through an example.
1, 3, 6, 10, 1 Subsequence
In Subsequence we can skip some elements but it should be done in increasing order, like 1 3 2 6 is
not subsequence. Order of elements in parent array should remain same in subsequence.
In the problem you have to find such subsequence which has 2 parts, whose first part is increasing in
order and second part is decreasing in order and it is the longest subsequence.
Here, (red is increasing subsequence and green is decreasing subsequence)
i) 1 2 3 8 9 10 2 1
ii) 1 2 3 6 7 9 10 2 1
are one of such subsequences but we can see that second subsequence is longest so we will choose
this one
1) Define a subproblem for it.
2) Provide its recurrence.
3) Pseudo code for the algorithm devised.
4) Run time complexity
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 3 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)