# Maximum Difference in an Array

##### January 14, 2024

## Problem #

Given an array of integers `nums`

, find the maximum difference between any two elements `nums[j]`

and `nums[i]`

such that `j > i`

.

**Example**:

- Input: nums = [7, 1, 5, 4] Output: 4 Explanation: The maximum difference is between 5 and 1.

## Solution Approach #

The solution involves iterating through the array while keeping track of the minimum element found so far and the maximum difference.

### Algorithm Steps #

- Initialize two variables:
`min_element`

to the first element and`max_diff`

to 0. - Iterate through the array starting from the second element.
- Update
`min_element`

if a new minimum is found. - Calculate the difference between the current element and
`min_element`

. - Update
`max_diff`

if the current difference is greater than`max_diff`

. - Return
`max_diff`

.

### Code (Python) #

```
def maxDifference(nums):
if len(nums) < 2:
return 0
min_element = nums[0]
max_diff = 0
for num in nums[1:]:
min_element = min(min_element, num)
max_diff = max(max_diff, num - min_element)
return max_diff
# Test the function
print(maxDifference([7, 1, 5, 4])) # Output: 4
```

### Time Complexity #

O(n), where n is the number of elements in the array. The array is traversed once.

### Space Complexity #

O(1), as no additional space is used apart from a few variables.