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.

  • $\begingroup$ 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$. $\endgroup$ – Paresh Jan 1 '13 at 3:36
  • $\begingroup$ corrected, typos !!! $\endgroup$ – nguyen Jan 1 '13 at 3:38
  • $\begingroup$ 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? $\endgroup$ – Paresh Jan 1 '13 at 3:42
  • 2
    $\begingroup$ Do you mean contiguous subarray, or do you mean subsequence? $\endgroup$ – JeffE Jan 1 '13 at 18:34
  • 1
    $\begingroup$ it is subsequence , and the array is discrete $\endgroup$ – 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$.

  • $\begingroup$ I have edited to iterate $j$ from $i$ instead of $i+1$. This will include all possible sub-arrays - even those of length 1. $\endgroup$ – Paresh Jan 1 '13 at 4:20
  • $\begingroup$ 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 ? $\endgroup$ – nguyen Jan 1 '13 at 4:39
  • $\begingroup$ Rather, can you give me an example where this is wrong? I assume $\alpha$ and $\beta$ are provided as input. $\endgroup$ – Paresh Jan 1 '13 at 4:48
  • $\begingroup$ 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 !!! $\endgroup$ – nguyen Jan 1 '13 at 4:54
  • $\begingroup$ 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. $\endgroup$ – Paresh Jan 1 '13 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.