Find all increasing/decreasing sub array

Question

I have a question that I still struggle with. It would be really appreciated if you guys could give me some hints.

Here is the problem : Assume that $a[1\dots n]$ is an array of $n$ positive real numbers. Let $\alpha >0$ and $\beta >0$

• a subarray $a_1$ with $m$ elements of $a[1 \dots n]$ is called increasing if $\frac{a_1[i]}{a_1[j]}\geq \alpha$, for all $i>j$ and $1 \leq i, j \leq m$.

• a subarray $a_2$ with $k$ elements of $a[1 \dots n]$ is called decreasing if $\frac{a_2[i]}{a_2[j]}\leq \beta$, for all $i>j$ and $1 \leq i, j \leq k$.

Question : write a program to find all increasing/decreasing subarrays of $a[1 \dots n]$ ? thanks so much for your help.

Answer 1

The question is not clear, you say sub-array, but in the comments you say sub-sequence, and also the comment "the array is discrete" (not sure what that means...).

It is also not clear whether you want a sub-sequence that is both increasing and decreasing. I will presume they are disjoint problems.

So, on the assumption that you want to find all increasing sub-sequences of the array: $a[i_1], a[i_2], \dots, a[i_m]$ with $i_1 \lt i_2 \lt \dots \lt i_m$ here is an algorithm.

Given the array $a[1, \dots n]$, you construct a directed acyclic graph of $n$ vertices: $v_i = (a[i], i)$ with a directed edge from $v_i$ to $v_j$ iff $a[j] \ge \alpha a[i]$ and $j \gt i$.

Now you enumerate all the paths in this directed graph. This is $O(n^2 + f(P))$ where $P$ is the number of paths in the graph, and $f$ is the complexity of the algorithm you pick to do the enumeration.

If you just wanted a count of paths rather than the actual paths themselves (which is what I suspect was your original problem, based on asking for a "hint"), then a dynamic programming algorithm which finds the number of sequences ending at a given $a[i]$ could be made to work in $O(n \log n)$ time.

Answer 2

Note: This answer was given before the OP substantially changed the question by requiring that the inequality holds for any pair of elements in the sub-array.

This is a basic brute force solution. Keep two nested for loops. In the outer loop, iterate the loop variable $i$ from $1$ to $n$. In the inner loop, iterate the loop variable $j$ from $i$ to $n$. Inside the inner loop, check for the ratio of $\frac{a[j]}{a[i]}$ and declare the sequence of $a[i \dots j]$ to be increasing or decreasing depending on the ratio in comparison with $\alpha$ or $\beta$.