Find all increasing/decreasing sub array

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.

-
If the array $a$ contains positive real numbers, how can any $\frac{a_2[k]}{a_2[1]}$ be negative? You have defined $\beta < 0$. –  Paresh Jan 1 '13 at 3:36
corrected, typos !!! –  nguyen Jan 1 '13 at 3:38
1. So basically the ratio of the last element of the sub-array to the first element has to be compared with $\alpha$ or $\beta$? 2. Is a brute force $\Theta(n^2)$ solution unacceptable? –  Paresh Jan 1 '13 at 3:42
Do you mean contiguous subarray, or do you mean subsequence? –  JeffE Jan 1 '13 at 18:34
it is subsequence , and the array is discrete –  nguyen Jan 2 '13 at 2:37

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.

-

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$.

-
I have edited to iterate $j$ from $i$ instead of $i+1$. This will include all possible sub-arrays - even those of length 1. –  Paresh Jan 1 '13 at 4:20
Hi Paresh, thaks for your answer I used your suggestion but it is not correct. You can check with random positive numbers. Can you give me more detail ? –  nguyen Jan 1 '13 at 4:39
Rather, can you give me an example where this is wrong? I assume $\alpha$ and $\beta$ are provided as input. –  Paresh Jan 1 '13 at 4:48
here is what I get n=10; let a=randn(1,n); al=0.8; beta=1.2; for i=1:1:n for j=i:1:n if a(j)/a(i)>al b=a(i:j): end end; the result was wrong when I computed by hand !!! –  nguyen Jan 1 '13 at 4:54
I do not have matlab, and won't be running code. Can you provide a concrete example (that can be solved by hand) and point out what is wrong in that case? That is, provide the array, the $\alpha, \beta$ values, and what is wrong there. –  Paresh Jan 1 '13 at 4:57