Chef Likes Good Sequences Codechef October Lunchtime Problem solution -
Lets read the problem statement carefully.
First of all do not confuse with subarray and subsequence.
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A subarray will always be contiguous but a subsequence need not be contiguous.
It's easy problem follow some simply step-
step 1- Calculate the longest subsequence in the initial array without changes.
Now think that if you made changes at xth position of array it will affect initial length if y!= a[x]
if y!=a[x] there occur some cases for which initial length may affect. You have to observe these cases and handle initial length accordingly.
- Case 1 : () and (), then answer will increase by as it will make segment into segments.
- Case 2 : () and (), then the answer will increase by as earlier and will introduce an extra segment. If then we will reduce the answer by as earlier we added as changing to increased the segment count but now it will be merged with previous segment. Example : let and , so If answer will increase by , and if then there will no change to the answer.
- Case 3 : () and (), similar to above case, we will increase the answer by . if then we will reduce the answer by .
- Case 4 : () and (), then if we will reduce answer by . if we will reduce answer by .(Note that you might reduce the answer by when ).
Must join my telegram channel -https://t.me/competitiveProgrammingDiscussion
Follow my code -