LDS

#include<stdio.h>
#include<string.h>

int n;
char seq[100];

int LIS();

int main()
{
    printf("Enter sequence size: ");
    scanf("%d",&n);
    printf("Enter the sequence:\n");
    scanf("%s",&seq);

    int ans=0;
    ans=LIS();
    printf("LDS: %d\n",ans);

    return 0;
}

int LIS()
{
    int i,j,lis[n];
    lis[0]=1;

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

    int max=0;
    for(i=0;i<n;i++)
        if(lis[i]>max)
            max=lis[i];

    return max;
}