## Maximum difference between two elements in the array such that larger element occurs after the smaller one.

**INPUT: 4 7 2 18 3 6 8 11 21**

**OUTPUT: ****19**

**ALGORITHM 1**

**TIME COMPLEXITY: **O(N)

**SPACE COMPLEXITY:** O(1)

We make use of the Kadane’s approach in a modified form.

- Initialize the current_difference as the difference of the first two elements.
- Loop through the array such that

- If the current_difference is greater than zero then add to it the difference of the consecutive array elements.(Compute Prefix Sum).
- Else current_difference is equal to the difference of the present consecutive elements.
- Compare the current_difference with the present max_difference and update it accordingly.

The approach uses Dynamic Programming and is very efficient.

#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {4,5,8,1,3,7,11,13,2}; int N = sizeof(arr)/sizeof(arr[0]); int diff = arr[1]-arr[0]; int curr_sum = diff; int max_sum = curr_sum; for(int i=1; i<N-1; i++) { // Calculate current diff diff = arr[i+1]-arr[i]; // Calculate current sum if (curr_sum > 0) curr_sum += diff; else curr_sum = diff; // Update max sum, if needed if (curr_sum > max_sum) max_sum = curr_sum; } if(max_sum >= 0) cout<<"Maximum difference is "<<max_sum<<endl; else cout<<"Maximum difference is not valid as array reversely sorted"<<endl; return 0; }

Try It

**ALGORITHM 2**

**TIME COMPLEXITY:** O(N^{2})

**SPACE COMPLEXITY:** O(1)

- Loop From the last of the array as we will have to check the larger number occurs later.
- Run another loop from start and do:

- If the present element is smaller than the number present at the index of the outer loop, then check if its difference is larger than the present difference.If yes then update the max_difference.
- Else increment the loop counter and check for the next difference.

#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {4,5,8,1,3,7,11,13,2}; int N = sizeof(arr)/sizeof(arr[0]); int max_diff = INT_MIN; for(int i=N-1; i>=0; i--) //start from the end so that we can check if the larger element comes later. { for(int j=0;j<i;j++) //select each number from start till one less than the number selected { if(arr[i] > arr[j]) //if the condition satisfies { if(arr[i] - arr[j] > max_diff) //update the max_diff max_diff = arr[i]-arr[j]; } } } cout<<"Maximum difference is "<<max_diff<<endl; return 0; }

Try It