## Introduction

Finding the maximum difference between two elements such that the larger element appears after the smaller number from a given array is a medium DSA implementation-based problem that can be solved using the concept of array traversal. Here first, we will discuss the brute force approach and then the optimized method.

Also See, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

We are given an array of integers. Help 'Ninja' to find the maximum difference between two elements where the larger element appears after the smaller element or find a[i] and a[j] such that a[j]-a[i] ( j > i ) is the maximum.

### Sample Examples

**Example 1**

**Input**

**Output**

Maximum difference: 8

**Explanation**

The maximum difference is 8 between 10 and 2.

**Example 2**

**Input**

**Output**

Maximum difference: 16

**Explanation**

The maximum difference is 16 between 19 and 3.

## Naive Approach

We simply use two nested loops in the basic technique. Taking each element one at a time and comparing it to all the others while keeping track of the largest difference elements where the larger element appears after the smaller element.

### Algorithm

- Traverse the array from left to right, and run a nested for loop for j=i+1.
- Declare a variable
*maxdifference*to store the maximum difference, and keep on comparing a[j] - a[i] for j>i. - Return the
*maxdifference*variable.

### Implementation in C++

```
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
//if the array is in decreasing order function returns -1
int max_diff(int a[], int n)
{
int maxdifference = a[1] - a[0];
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
if (a[j] - a[i] > maxdifference)
maxdifference = a[j] - a[i];
}
}
return maxdifference;
}
int main()
{
int arr[] = {2, 5, 4, 10, 4, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum difference : ";
cout<< max_diff(arr, n);
return 0;
}
```

**Output**

#### Time Complexity Analysis

The time complexity is O(n^2) because we are using two nested loops.

#### Space complexity Analysis

Because we don't use auxiliary space, the space complexity is O(1).