How to find the max difference of 2 elements in a array given some constraints?

Problem: Find the maximum difference of 2 elements in an array such that the index of the element of the larger element is greater than the index of the smaller element.

Note: I will use zero-based indexing.

Example:

array = {1,2,3,4,5}

The maximum difference will be 4. The index of '5' is greater than the index of '1', and it has the maximum difference in sum (5 - 1 = 4).

Example 2:

array = {5,3,2,4,6}

The maximum difference of this array will be 4. The index of '6' is greater than the index of '2', and it has the maximum difference in sum (6 - 2 = 4).

I have tried implementing a brute force solution but it runs of O(n^2).

int main(){    int n = 5;    int arr[n] num_array = {1,2,3,4,5};    int maximum_value = 0;    for (int i=0;i<n;i++){      for (int j=i+1;j<n;j++){        if (num_array[j] - num_array[i]>maximum_value)         {          maximum_value = num_array[j] - num_array[i];        }      }    }      }  

This solution gives Time Limit Exceeded (TLE) and I could not find a way to optimise it.

https://stackoverflow.com/questions/65519743/how-to-find-the-max-difference-of-2-elements-in-a-array-given-some-constraints December 31, 2020 at 06:38PM