LAUGHMEN - Editorial

Observation 1: If J_i = -1, then there is no benefit of making J_i = 1 because that way the array containing laughing intensity of good jokes will have more elements. If this array was earlier sorted, it might as well become sorted, in the best case, it will remain sorted itself (no change of its already sorted status), while if the earlier array was not-sorted, then adding more elements into it can’t make it sorted.

So, we create the array of intensities over good jokes. We want this array to be sorted. For that, we are allowed to delete at most one of the elements in it. This is equivalent to checking whether the length of a longest increasing subsequence in the array is n-1.

One can go through the array and find the first place where a_i > a_{i + 1}, then one has to delete either of a_i or a_{i+1}. We can try deleting both of these and check whether the updated array is indeed sorted or not.