PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
MEDIUM
PREREQUISITES:
DYNAMIC PROGRAMMING, SEGMENT TREES
PROBLEM:
Find the length of the longest alternating subsequence of a given sequence as well as the number of longest alternating subsequences.
EXPLANATION:
Subtask 1 can be solved by iterating through all subsequences as usual.
Subtask 2 can be solved using a simple dp. The idea is to let dp[i][1] denote the longest alternating subquence ending at i and the last element is larger than the second last element as well as the number of such subsequences. Define dp[i][0] similarly except now the last element is smaller than the second largest element. Thus, we can form a simple recurrence for dp as in finding the longest increasing subsequence. For example, dp[i][0] = \max_{a_{j} < a_{i}}(dp[j][1]) + 1 and we can update the number of such subsequences by summing the number of subsequences stored in all dp[j][1] that achieves the maximum value. This solution is O(n^{2}).
Subtask 3 is just an extension of this idea. Iterating through all j is inefficient. Instead, we can construct a segment tree where the i-th element stores the current dp value of this element. You can now transform the recurrence given in Subtask 2 into a range query of the segment tree and we can update the corresponding element in the segment tree after each step. It is advisable to refer to the code for the details. The time complexity will be O(n\log n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.