Problem Link - Interesting Sequences
Problem Statement
You are given N integers in an array: A[1], A[2], \ldots, A[N]. You also have another integer L.
Consider a sequence of indices (i_1, i_2, \ldots, i_k). Note that a particular index can occur multiple times in the sequence, and there is no order in which these indices have to occur. (i_1, i_2, \ldots, i_k) is a sequence of size k. It is said to be an Interesting sequence, if A[i_1] \ge A[i_2] \ge \ldots \ge A[i_k].
The Cost of an Interesting sequence (i_1, i_2, \ldots, i_k), is defined to be the minimum absolute difference between any two adjacent indices. In other words, the Cost is min \{ |i_2 - i_1|, |i_3 - i_2|, \ldots, |i_k - i_{k-1}| \}.
Your job is to consider the Costs of all the Interesting sequences of size L associated with the given array, and output the maximum Cost. Note that you can show that there is always at least one Interesting sequence for the given constraints.
Approach
To solve this problem, the idea is to use binary search to find the maximum possible cost of any Interesting sequence. The binary search range goes from 1 to N (the size of the array), as the cost is defined by the absolute difference of indices. For each middle point in the binary search, we need to check if there is any Interesting sequence of size L with a minimum gap between indices greater than or equal to this middle value. This check is done using dynamic programming: for each element in the array, we calculate the maximum length of any valid sequence ending at that element, ensuring that the indices satisfy the gap condition. If we find a valid sequence or a matching element that meets this condition, we update the answer and increase the search range; otherwise, we reduce the range. The final answer will be the maximum cost found during the search.
Time complexity
O(N^2 \log N), where N is the size of the array.
Space complexity
O(N) for storing the dynamic programming array.