Not getting correct answer
You shouldn’t be changing left and rightmost value of a[i]'s lcs only update a[i] and that too left value +1 .I have mentioned these changes in comment.
Still in doubt. Because we need to reflect the change (streak length) in the left boundary as well as the right boundary. Also the length of the streak has to be lenl+1+lenr. These were told in the video, and seems like the correct approach. Please elaborate. I’m not able to comprehend why we did that.
You have taken right elements of current element as well.But we here want subsequence so if you are currently getting 5 say then 6 should come after 5 and not before 5.You have included 6 in subsequence if it comes before 5 which is wrong.You should find 5 first then 6.
I would suggest you to go through this link for further implementation details:
In the sample test case in leetcode too 4 is present before 1, 2, 3. But it is still being included when calculating the answer. I have used map for that very purpose. In the GFG solution, theyve used DP. And I’ve not studied DP. Please help me finding the answer using this approach.
If you don’t know dp then what you can do is insert all elements in a set first then run a loop from 0 to n-1 and find the maximum subsequnce with this element as starting element.
It will be an O(n^2) solution.
To make it O(n) what you can do is first check if current element -1 is in the set or not,if not then only run second loop.Please implement it this way.The observation for this is that is current element -1 exists then it will give us a better solution so then we will use that answer