Highest Percentage Increase

Question

Lets say we have the following set of numbers representing values over time

1 2 3 10 1 20 40 60

Now I am looking for an algorithm to find the highest percentage increase from one time to another. In the above case, the answer would be the pair (1, 60), which has a 6000% increase.

So far, the best algorithm I can think of is a brute-force method. We consider all possible pairs using a series of iterations:

1st Iteration:

1-2 1-3 1-10 .. 1-60

2nd Iteration

 2-3 2-10 2-1 ... 2-60

(etc.)

This has complexity O(n³).

I've also been thinking about another approach. Find all the strictly increasing sequences, and determine only the perecentage increase in those strictly increasing sequences.

Does any other idea strike you guys? Please do correct me if my ideas are wrong!

Answer 1

If I understand your problem correctly, you are looking for two indices (i, j) in the array with i < j that has the highest ratio A[j]/A[i]. If so, then you can reduce it to this related problem, which asks you to find the indices (i, j) with i ≤ j such that A[j] - A[i] is as large as possible. That problem has a very fast O(n)-time, O(1)-space algorithm that can be adapted to this problem as well. The intuition is to solve the problem for the array consisting of just the first element of your array, then for the first two elements, then the first three, etc. Once you've solved the problem for the first n elements of the array, you have an overall solution to the problem.

Let's think about how to do this. Initially, when you consider just the first element of the array, the best percentage increase you can get is 0% by comparing the element with itself. Now, suppose (inductively) that you've solved the problem for the first k array elements and want to see what happens when you look at the next array element. When this happens, one of two conditions holds. First, the maximum percentage increase over the first k elements might also be the maximum percentage increase over the first (k + 1) elements as well. For example, if the (k+1)st array element is an extremely small number, then chances are you can't get a large percentage increase from something in the first k elements to that value. Second, the maximum percentage increase might be from one of the first k elements to the (k + 1)st element. If this is the case, the highest percentage increase would be from the smallest of the first k elements to the (k + 1)st element.

Combining these two cases, we get that the best percentage increase over the first k + 1 elements is the maximum of

• The highest percentage increase of the first k elements, or
• The percentage increase from the smallest of the first k elements to the (k + 1)st element.

You can implement this by iterating across the array elements keeping track of two values - the minimum value you've seen so far and the pair that maximizes the percent increase. As an example, for your original example array of

1  2  3  10  1  20  40  60

The algorithm would work like this:

       1       2       3       10        1       20       40        60
min        1       1        1       1       1         1        1        1
best     (1,1)   (1, 2)  (1, 3)  (1, 10)  (1, 10)  (1, 20)   (1, 40)  (1, 60)

and you'd output (1, 60) as the highest percentage increase. On a different array, like this one:

3   1   4   2   5

then the algorithm would trace out like this: 3 1 4 2 5 min 3 1 1 1 1 best (3,3) (3,3) (1,4) (1,4) (1,5)

and you'd output (1, 5).

This whole algorithm uses only O(1) space and runs in O(n) time, which is an extremely good solution to the problem.

Alternatively, you can think about reducing this problem directly to the maximum single-sell profit problem by taking the logarithm of all of the values in your array. In that case, if you find a pair of values where log A[j] - log A[i] is maximized, this is equivalent (using properties of logarithms) to finding a pair of values where log (A[j] / A[i]) is maximized. Since the log function is monotonically increasing, this means that you have found a pair of values where A[j] / A[i] is maximized, as intended.

Answer 2

So you just want to compare each number pair-wise and see which pair has the highest ratio from the second number to the first number? Just iterating with two loops (one with i=0 to n, and an inner loop with j=i+1 to n) is going to give you O(n^2). I guess this is actually your original solution, but you incorrectly said the complexity was O(n^3). It's n^2.

You could get to O(n log n), though. Take your list, make it into a list where each element is a pair of (index, value). Then sort it by the second element of the pair. Then have two pointers into the list, one coming from the left (0 to n-1), and the other coming from the right (n-1 to 0). Find the first pair of elements such that the left element's original index is less than the right element's original index. Done.

1 2 3 10 1 20 40 60
becomes
(1,0) (2,1) (3,2) (10,3) (1, 4) (20, 5) (40, 6) (60,7)
becomes
(1,0) (1,4) (2,1) (3,2) (10,3) (20,5) (40,6) (60,7)

So your answer is 60/1, from index 0 to index 7.

If this isn't what you're looking for, it would help if you said what the right answer was for your example numbers.

Answer 3

I may have misunderstood the problem, but it seems that all you want is the largest and smallest numbers, since those are the two numbers that matter.

while true:
    indexOfMax = max(list)
    indexOfMin = min(list)
    list.remove(indexOfMax)
    list.remove(indexOfMin)
    if(indexOfmax < indexOfMin)
        contine
    else if(indexOfMax == indexOfMin)
        return -1
    else
        SUCCESS

Answer 4

As I understand (you didn't correct me in your comment), you want to maximize a[i]/a[j] for all j <= i. If that's correct, then for each i we only need to know smallest value before it.

int current_min = INFINITY;
double max_increase = 0;
for (int i = 0; i < n; ++i) {
    current_min = min(current_min, a[i]);
    max_increase = max(max_increase, a[i] / min);
}