Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in array.
Examples: If array is [2, 3, 8, 6, 4, 8, 1] then returned value should be 6 (Diff between 8 and 2). If array is [ 7, 9, 5, 6, 13, 2 ] then returned value should be 8 (Diff between 5 and 13)
Method 1 (Brute Force)
Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.
Time Complexity: O(n2)
Method 2
In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far.
2) Minimum number visited so far.
int maxDifference(int arr[], int n) { int min_element=arr[0]; int diff=arr[1]-arr[0]; for(i=1;i<n;i++) { if(arr[i]-min_element>diff) diff=arr[i]-min_element; if(arr[i]<min_element) min_element=arr[i]; } return diff; }
Time Complexity: O(n)
this problem is nothing but Stock Sell Maximize profit. Just use that logic here.