Question

Scheme Programming

Write a polynomial time scheme program to find the longest non-decreasing subsequent of a list of numbers. For example:

(longest ''(2 4 3 1 2 1 3 6 1 3 2 1 2 33 4 2 4 10 11 7)) --> (1 1 1 1 2 4 4 10 11).

Do not use side-effecting functions (i.e., functions with exclamation point in their names such as set!), sequencing, iteration (e.g., do, for-each) or vectors. Do not use input/output mechanisms other than the regular read-eval-print loop. You are allowed to use some additional built-in list operations, e.g., reverse, list-ref, map, list, let, let*, length, append, cons, car, cdr, boolean operations, null?, equal?, etc.

Answer 1

Time complexity : O(n^2) - polynomial

#include<bits/stdc++.h> 
using namespace std; 
        
/* lis() returns the length of the longest increasing subsequence in arr[] of size n */

int lis( int arr[], int n ) 
{ 
        int lis[n]; 

        lis[0] = 1; 

        for (int i = 1; i < n; i++ ) 
        { 
                lis[i] = 1; 
                for (int j = 0; j < i; j++ ) 
                        if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) 
                                lis[i] = lis[j] + 1; 
        } 

        return *max_element(lis, lis+n); 
} 
        
int main() 
{ 
        int t;
    cin>>t;
    while(t--)
    {
        int n;
    cin>>n; 
        int arr[n]; 
        for(int i=0;i<n;i++)
    {
       cin>>arr[i];
    } 
        
    printf("Length of lis is %d\n", lis( arr, n ) ); 
    }
        return 0; 
}