Maximum difference in an array

Today lets look into the maximum difference in an array
problem

find the maximum difference in the array array[j] - array[i],where j>i

we can solve this by using

1. O(n²) 2 for loop method
2. O(n) efficient solution

lets look into first one

int maxDif(int[] arr) {
    int maxDif = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] - arr[i] > maxDif) {
          maxDif = arr[j] - arr[i];
        }
      }
    }
    return maxDif;
  }

we are going to create maxDif variable and initialise it with
Integer.MIN_VALUE
next we are going to iterate the array using for loop (i loop)
inside that i loop we are going to iterate all the elements present at the right side only due to the condition j>i we are going to start the j loop with i+1, for each element we are going to find the difference and if the difference is greater than the maxDif we will assign that value to it

Time complexity:- O(n²)

lets look into another method

int maxDifEfficient(int[] arr) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length - 1; i++) {
      max = Math.max(max, arr[i + 1]); 
      min = Math.min(min, arr[i]);
    }
    return max - min;
  }

the logic behind this method is max difference is possible if we subtract between the largest number and the smallest number
so we need to find the largest and smallest number in the array with j>i condition
here we are trying to solve the problem in O(n) for that we are using min and max variables with values Integer.MAX_VALUE, Integer.MIN_VALUE respectively
we iterate the array find which is the max and min value

we find max using Math.max(max,arr[i+1]); here j is i+1 since i+1 is greater than i we satisfy the j>i condition

and we find the min using Math.min(min,arr[i])

once the loop is completed we will have the largest and smallest number in the array with respect to j>i condition and we can subtract that to find the maximum Difference.

Time complexity:- O(n²)