Discrete Mathematics Devise an algorithm that takes as input

Discrete Mathematics

Devise an algorithm that takes as input a list of n integers in unsorted order, where the integers are not necessarily distinct, and outputs the location (index of first element) and length of the longest contiguous non-decreasing subsequence in the list. If there is a tie, it outputs the location of the first such subsequence. Express your algorithm in pseudocode. For the list 9, 7, 9, 4, 5, 8, 1, 0, 5, 9, what is the algorithm’s output? How many comparison operations between elements of the list are used?

Solution

This is the very famous Dynamic Programming Problem, the objective is to find the length of the longest increasing subsequence

Let us assume that we know that the given L[i] is the list of increasing element subsequence in array of n elements,then we can recursively call

If element at ith position > element at the jth position and list[i] <= list[j] + 1

then we can equate list[i] = list[j]+1

If no such exists then the answer would be 1, hence we need to start with all the element of list array as 1

List: 9, 7, 9, 4, 5, 8, 1, 0, 5, 9

The length of Longest increasing subsequence is equal to 4