In this article, we look at a problem : Given an Array of Positive Integers, Find the [Maximum Difference](https://java2blog.com/maximum-difference-between-two-elements-in-array/ "Maximum Difference") between Two Adjacent Numbers
.
For each pair of elements we need to compute their difference and find the Maximum value of all the differences in array.
Let us look at an example, Consider this array:
For the above shown array, we have to solve the given problem. Here are the steps which we will follow for the implementation:
- Firstly, for each pair of elements, we have calculated their difference. We have calculated the Absolute Value of their difference because the array is not sorted and elements on either side can be greater or smaller.
- In the figure above, we have shown the Diff. value for each such pair. We need to find the Maximum Value among these which for the above case is :
11
for the pair(1,12)
. - We are going to iterate through the array, Arr starting from index 1 and calculate the current difference for each pair as :
Arr[i]>Arr[i] - Arr[i-1]
code>. We have amax_diff
variable which maintains the maximum of all the differences, on each iteration we update themax_diff
with current difference.
Note:
To calculate the Absolute Value we use Math.abs()
in java. The approach is for only Positive Values in the array.
Now, let us have a quick look at the implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.*; public class Maximum_Adjacent_Difference { public static void main(String args[]) { // Initialize array with Positive Values. int arr[] = new int[]{5,0,10,2,3,6,8,1,12,7}; // get the size of array. int n= arr.length; int result = maxDifference(arr,n); System.out.println("The Maximum Difference between Two Adjacent Numbers in the Array is : "+ result); } public static int maxDifference(int arr[], int n) { int max_diff = Integer.MIN_VALUE; for(int i=1;i<n;i++) { // For each pair we calculate the Difference. int curr_diff = Math.abs(arr[i]-arr[i-1]); // Update max_diff if current pair value is the greatest till now. max_diff = Math.max(max_diff,curr_diff); } return max_diff; } } |
Output:
1 2 3 |
The Maximum Difference between Two Adjacent Numbers in the Array is : 11 |
We implement the same example discussed above in code. Let us analyze the complexity of the code.
Time Complexity:
We do a simple single traversal of the array which takes linear time so the time complexitiy is O(n)
, for n elements in array.
That’s it for the article you can try out this code with different examples and let us know your suggestions or queries.