MERGEDLIS - Editorial

editorial
, , ,
44

I have used the same approach and got WA.
Can anyone pls tell on which test case it is failing…

45

Can you pls tell me on which test case will the code will fail?
Your and mine, both approaches are exactly the same.

46

A=[1,1,4,7,2,2,3,3]
B=[3,6,4,5]
Correct Answer :- 6+3=9
Your Answer :- 4+2=6

1 Like
47

Try this :

1 4 1 3
2 3

Correct output : 5 ( one possible way to merge : 𝟭 𝟰 𝟭 2 3 𝟯 )

1 Like
48

can anyone tell me why this code is not accepted?

import java.util.*;

public class Main
{
static int fun(int a[],int n)
{
int max=1;
int len=1;
for(int i=1;i<n;i++)
{
if(a[i]>=a[i-1])
len++;
else{
if(max<len)
max=len;
len=1;
}

        }
        if(max<len)
        max=len;
        return max;
}
public static void main(String args[])
{
    Scanner input=new Scanner(System.in);
    int t=input.nextInt();
    while(t--!=0)
    {
        int n=input.nextInt();
        int m=input.nextInt();
        int a[]=new int[n];
        int b[]=new int[m];
        for(int i=0;i<n;i++)
        {
            a[i]=input.nextInt();
        }
        for(int j=0;j<m;j++)
        {
            b[j]=input.nextInt();
        }
        System.out.println(fun(a,n)+fun(b,m));
    }
}

}

49

Because you are calculating Longest Non Decreasing SUBARRAY and not SUBSEQUENCE .
Use Patience Sort Algorithm to find LNDS in O(nlogn) time

50

Thanks a lot…!!!
Now I got where it’s getting wrong

51

Thanks a lot…!!!
I got it now…

52

But if the resultant array is
1 1 3 4 6 7 2 2 3 3 4 5
then and should be 12
but you are telling and and = 9
How???

53

the resultant array is 1 4 1 2 3 3
so all elements are in increasing order
so ans should be 6.
How it is 5 ??

54

How did you get the resultant array as 1 1 3 4 6 7 2 2 3 3 4 5 ?

It should be 1,1,4,7,2,2,3,3,3,6,4,5

1 Like
55

You have to find the LNDS length, NOT the resulting array length .

so all elements are in increasing order

1 → 4 → 1 …
How increasing??

56

Wait wait wait…!!!
oh I was taking the question in wrong manner.
I was thinking like
we need to make small small continuous increasing subsequences and output the sum of length of all of that…

But Now I got we need to make a non-continuous increasing subsequence and output the lenght of that increasing subsequence.
Thanks You So Much for ur help Bro.

57

yes you are right, sorry to take your time. but it cleared a doubt, which i thought i didn’t have.