Mathematical Computation Problem | Progressive Sequence | Codewindow.in

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

Recent Posts
Pages