**Problem Statement:** Given an array of integers of size **N**, Our task is to find the maximum difference between two numbers such that **(i < j) **i.e Order should be maintained.

**Examples**:

Example 1:Input:N = 7, array[] = {2, 3, 10, 6, 4, 8, 1}Output: 8Explanation:Here the maximum element is 10 and the minimum element is 2, Both elements satisfy the condition (i < j), So the difference between maximum and minimum is always maximum so the answer is (10 - 2) = 8.Example 2:Input:N = 5, array[] = {100, 1, 2, 5, 100}Output: 99Explanation:Here the maximum element is 100 and the minimum element is 1, Both elements satisfy the condition (i < j), So the difference between maximum and minimum is always maximum so the answer is (100 - 1) = 8.

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: Naive Solution**

- We will use two nested loops.
- The outer loop will help to pick up elements one by one.
- The inner loop starts from the next index of the picked element. Calculate the difference of the picked element with every other element in the array.
- Compare the difference with the maximum difference current maximum difference calculated so far.
- At the end return, the maximum difference is calculated.

**Code**:

## C++ Code

```
#include<bits/stdc++.h>
using namespace std;
int maxDiff(int arr[], int n) {
int res = arr[1] - arr[0];
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
res = max(res, arr[j] - arr[i]);
}
}
return res;
}
int main() {
int arr[] = {2, 3, 10, 6, 4, 8, 1}, n = 7;
cout << "The maximum difference with order is: " << maxDiff(arr, n);
}
```

**Output:** The maximum difference with order is: 8

**Time Complexity: O(N^2)**

**Space Complexity: O(1)**

## Java Code

```
class TUF {
static int maxDiff(int arr[], int n) {
int res = arr[1] - arr[0];
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
res = Math.max(res, arr[j] - arr[i]);
}
}
return res;
}
public static void main(String args[]) {
int arr[] = {2,3,10,6,4,8,1}, n = 7;
System.out.println("The maximum difference with order is: " + maxDiff(arr, n));
}
}
```

**Output:** The maximum difference with order is: 8

**Time Complexity: O(N^2)**

**Space Complexity: O(1)**

**Solution 2: Efficient Solution (Single traversal)**

- In this approach, we will keep track of
**two**things. - First, We will keep track of the
**Maximum difference**so far. - Second, We will keep track of the
**minimum element**we have found so far. - So, we will initialize the maximum difference as
**arr[start+1] – arr[start]**. - And for the minimum value that will be initialized as
**arr[start].** - If
**arr[i] – minimum**value is greater than the maximum difference so far,**then we will update the maximum difference with this new value.** - If
**arr[i]**is less than the minimum element we found so far then we will**update the minimum value with arr[i].** - After traversing the array in the above manner at last we will be left with the maximum difference with the order.
- Print / Return it.

**Dry Run Implementation:**

**Code:**

## C++ Code

```
#include <bits/stdc++.h>
using namespace std;
int maxDiff(int arr[], int n) {
int res = arr[1] - arr[0], minVal = arr[0];
for (int i = 1; i < n; i++) {
res = max(res, arr[i] - minVal);
minVal = min(minVal,arr[i]);
}
return res;
}
int main() {
int arr[] = {2, 3, 10, 6, 4, 8, 1}, n = 7;
cout << "The maximum difference with order is: " << maxDiff(arr, n);
}
```

**Output:**

**Output: The maximum difference with order is: 8**

**Time Complexity: O(N)**

**Space Complexity: O(1)**

## Java Code

```
class TUF {
static int maxDiff(int arr[], int n) {
int res = arr[1] - arr[0], minVal = arr[0];
for (int i = 1; i < n; i++) {
res = Math.max(res, arr[i] - minVal);
minVal = Math.min(minVal, arr[i]);
}
return res;
}
public static void main(String args[]) {
int arr[] = {2, 3, 10, 6, 4, 8, 1}, n = 7;
System.out.println("The maximum difference with order is : " + maxDiff(arr, n));
}
}
```

**Output:**

**Output: The maximum difference with order is: 8**

**Time Complexity: O(N)**

**Space Complexity: O(1)**

Special thanks toplease check out this articlefor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,Abhishek Yadav