Give an On2time algorithm to find the longest monotonically

Give an O(n^2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.

Solution

An O(n^2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers :-

Let A[0..n-1] be the input array and LIS[0..n-1] be used to store lengths of longest increasing subsequences ending at LIS[i] for each i.

LIS[i] = 1, 0 <= i < n
for i = 1 to n-1:
for j = 0 to i-1:
    if A[i] > A[j] and LIS[j] + 1 > LIS[i]:
     LIS[i] = LIS[j] + 1
Required solution = max(LIS[i], 0<=i<n)

The time complexity of the above solution is O(n^2).

Example :

Arrary = { 10, 22, 29, 33, 21, 50, 41, 60, 70 }