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.
Example
Input:
4
1 1 2 1
Output:
1 1 2
Solution: In C
#include <stdio.h>
int main()
{
int previous_len=0,n,a[100], start=0, c[10], len=0;
scanf("%d",&n);
for(int i=0; i<n;i++)
scanf("%d",&a[i]);
for (int i=0; i<n-1; i++) {
if(a[i+1] > a[i]) {
len++;
if (len > previous_len) {
previous_len=len;
start=i-len;
}
} else {
previous_len=len;
len=0;
}
}
for(int i = 0; i <= previous_len+1; ++i) {
c[i]=a[start+i];
printf("%d ",c[i]);
}
return 0;
}Solution: In Java
import java.util.ArrayList;
import java.util.Scanner;
class LongestProgressiveSequence {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
ArrayList<Integer> ls = new ArrayList<Integer>();
Integer[] temp = new Integer[0];
for (int i = 0; i < t; i++) {
int num = sc.nextInt();
if (!(ls.isEmpty())) {
if (num >=ls.get(ls.size()-1 )) {
ls.add(num);
} else {
if(ls.size()>temp.length)
temp=ls.toArray(temp);
ls.clear();
ls.add(num);
}
} else {
ls.add(num);
}
}
if(ls.size()>temp.length)
{
temp=ls.toArray(temp);
ls.clear();
}
for (int i = 0; i < temp.length; i++) {
if(i<temp.length-1)
System.out.print(temp[i]+" ");
else
System.out.println(temp[i]);
}
}
}Solution: In Python 3
class Solution(object):
def lengthOfLIS(self, nums):
tails =[0 for i in range(len(nums))]
size = len(nums)
for x in nums:
i=0
j=size
while i!=j:
mid = i + (j-i)//2
if tails[mid]< x:
i= mid+1
else:
j = mid
tails[i] = x
size = max(i+1,size)
return tails
ob1 = Solution()
n = int(input())
num = list(map(int, input().split(' ')))
print(ob1.lengthOfLIS(num))Also Checkout