Find the greatest decreasing and increasing

Question

I want to find greatest decreasing and increasing percentage. I think my codes work but i want to find more fast way. Because i try my code with random cases in 2 second. And my success rate %33. In other cases i took timeout error because i put 2 second limit. (If there isn't decreasing or increasing, result have to be -1)

void maxmin(double* arr, int n) {
    double max = -1;
    double min = -1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i+1; j < n; j++) {
            double temp = ((arr[i] - arr[j]) / arr[i]);
            if (temp > 0) {
                if (min == -1)
                    min = temp;
                else if (min < temp)
                    min = temp;
            }
            else {
                if (max == -1)
                    max = temp;
                else if (max > temp)
                    max = temp;
            }
        }
    }

    if (max != -1)
        max = max * (-1);
    
    if (min == -1)
        printf("%.10f\n", min);
    else
        printf("%.10f\n", min*100);
    
    if (max == -1)
        printf("%.10f\n", max);
    else
        printf("%.10f\n", max*100);

}

The time complexity of the code above is O(n²). You should rather look for a more efficient algorithm than optimizing this code. — M. Nejat Aydin, Aug 16 '20 at 21:27

score 1 · Answer 1 · answered Aug 16 '20 at 20:58

The problem with your algorithm is that it takes O(n^2) time. You can make an observation though: When you are processing a[i], you only care about the minimum and maximum value of a[j]'s that you have encountered before.

Therefore, you can make your algorithm take O(n) time by maintaining the max and min of a[j]s you've seen so far.

Pseudo-code:

min_aj := a[0]
max_aj := a[0]
for i = 1, ..., n - 1:
  1. only consider (a[i] - min_aj)/a[i] and (a[i] - max_aj)/a[i]
  2. now, min_aj = min(min_aj, a[i])
  3. and, max_aj = max(max_aj, a[i])

Josh Purtell · Answer 2 · 2020-08-16T20:42:16.673

Kudos on optimizing the indexing. I would recommend converting some of your if-else blocks into switch statements, which can help with runtime. See the following for more discussion: Advantage of switch over if-else statement.

Additionally, it might be worthwhile to just initialize max=-1 and min=10000000 (or some other sufficiently large number) and compare directly with the element, which may help you avoid some if-else logic.

That is (on the latter count), opt for something like:

double max;
max=-1;
double min;
min=100000;

for (int i = 0; i < n - 1; i++) {
        for (int j = i+1; j < n; j++) {
            temp=((arr[i] - arr[j]) / arr[i]);
            if (temp>max){
                max=temp;
            if (temp < min) {
                min=temp;
            }
        }
    }
}

To clean up the logic structure. I'll leave the conversion to switch statements to you. Good luck!

Find the greatest decreasing and increasing

2 Answers2