in this problem i was printing the max decreasing subsequence of the vector of unrepeated elements (in the same order as that of array) from that array.
can anyone please tell me why is it wrong .
i was only considering the first occurence of a value . and if it comes again it wont be included in the vector.
so if i have like 4 3 2 1 the answer will be 4 because we need to have 4 repeatitions of 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 to get that maximum length subsequence 1 2 3 4
thanks.
i have just find out the maximum increasing subsequence in the array and deleted the length of this subsequence from the total no. of distinct elements and printed the answer + 1.
can any body please tell what is the mistake in this approach.
what wiil be your answer for 5 1 1 5.
4 5 2 3 1
your answer 4
answer is 3
1
no my answer is 3 only
bro no… is 4 5 2 3 1 LIS length is 2 , distinct element is 5 acc to ur approach 5-2+1 = 4
ya bro sorry i was wrong
logic was to find all increasing subsequences which starts from element which is not part of the any increasing subsequence.
like for following array
1 4 1 5 3 2 1 3
we have to find all increasing subsequnces
1 2 3
4 5
and hence ans will be 2
1 Like
Although I was not able to code
but I think it can be done in following way
find all unique elements sort them in different array.
find as many element of this array that you can find in given array remove those elements and increase ans by 1
repeat until you find all the elements of sorted array.
but I guess it will give TLE
I submitted my solution with map in c++ it got TLE and after contest I just changed map to unordered_map and it gave AC. I wasted 30 mins in this question . . . RIP