Author: | Adrian Miclaus |
Solved by: | |
First to solve: | LNTU_IPZ_3 |
In this problem, we need to determine the longest subsequence with the property that it can be divided into blocks of equal elements of length at least 2. The main observation is that such a subsequence can be divided into blocks of equal elements of length 2 or 3. Thus, we can solve the problem by dynamic programming. Let be the length of the longest subsequence with the property mentioned above in the prefix s_1, s_2, \dots, s_i. We start by initializing dp[0] = dp[1] = 0. Then, can be computed with the following recurrence:
To fill the array we need to iterate from to and keep the last occurrence of each element. This can be done with an unordered_map/ map resulting in an algorithm of complexity O(n) / O(n \log{n}). The answer is .