Maximum Difference in An Array
Find the difference between any two elements in an array arr of integers such that the larger element appears after the smaller number in the array.
For example, if the array contains the elements [2, 3, 8, 6, 4, 8, 1], the returned value should be 6. (Diff between 8 and 2). The returned value should be 8 if the sequence is [ 7, 9, 5, 6, 13, 2 ]. (Diff between 5 and 13)
1st method (Brute Force) Maximum Difference in An Array
Make use of two loops. Pick elements one by one in the outer loop, then calculate the difference between the selected element and every other element in the array in the inner loop and add it to the maximum difference measured so far.
Complexity of Time: O (n2)
Method number 2 – Maximum Difference in An Array
Instead of comparing the selected element to any other element, we use this approach to compare it to the smallest element found so far. As a result, we must keep track of two things:
1) So far, the greatest difference has been discovered.
2) The smallest number of people who have been so far.
Time Complexity: O(n)
- Asynchronous Data Transfer in Computer Architecture
- Connection-Oriented and Connectionless Services
- Data Reduction in Data Mining
- Contiguous Memory Allocation
- Longest Substring Without Repeating Characters