Question

Sequence (Longest Progressive Sequence) in C language

Given a sequence, the objective is to find the longest progressive sequence arranged in ascending order. Detailed descriptions are as:

Problem
A sequence is said to be progressive if it doesn’t decrease at any point in time.
For example 1 1 2 2 is a progressive sequence but 1 2 1 is not a progressive sequence. Let S be the sequence and be represented by L spaced integers Ki, now your task is to find out the first longest progressive sequence present in the given sequence (S).

Input Format:

First line will contain T, the length of the sequence and next line will contain T spaced integers Ki (where i = 0,1, …,L).
Line 1 T,where T is the length of the sequence
Line 2 Ki,where Ki is integer in sequence separated by space

Constraints:

1<=T<=10^6(one million)
1<=Ki<=10^9(one billion)

Output Format:

Line 1 longest progressive sequence present in the given sequence

Answer 1

Solution:

I have used int to declare T,while long for Array since is of 10^9.

Program:

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

int main()
{
   //Number of elements in sequence
   int T;
   scanf("%d",&T);
   //Array to store t number of values .
   //Long data type is used since Ki is of range 10 power 9
   long seq[T];
   //Values to store longest subsequence length,subsequnce length and start index of increasing subsequence
   int i=0,subseqlen=0,maxsubseqlen=0,start=0;
  
   for(i=0;i<T;i++)
       scanf("%ld",&seq[i]);
  
   for(i = 0; i < T-1; i++)
   {
       //If progressive
       if(seq[i]<=seq[i+1])
       {
           subseqlen++;
           //Calculating maxsubseqlen and starting point
           if(subseqlen>maxsubseqlen)
           {
               maxsubseqlen=subseqlen;
               start=i+1-subseqlen;
           }
       }
       else
       {
           subseqlen=0;
       }
   }
   int subseq[maxsubseqlen+1];
   for(i=0;i<=maxsubseqlen;i++)
   {
       subseq[i]=seq[start+i];
       printf("%d ",subseq[i]);
   }
  
   return 0;

}

Output: