Maximum difference between two elements such that larger element appears after the smaller number

Dynamic Programming Approach

We can use a modified version of Kadane's algorithm. The method is quite effective and involves dynamic programming.

Kadane’s Algorithm

1. From right to left, traverse the array.
2. Use two variables: maxDifference (final answer) and currSum which stores the first two items' differences.
3. Compute Prefix Sum.
   1. if (current difference > zero), Add the difference between the following array members.
   2. else: current difference is equal to the current consecutive element’s difference.
4. Compare the sum of current differences with maxDifference and update accordingly.
5. Return the maxDifference as the final answer.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int max_diff(int arr[], int n)
{
    int diff = arr[1]-arr[0];
    int curr_sum = diff;
    int maxDifference = curr_sum;
    
    for(int i=1; i<n-1; i++)
    {
        // Calculate the current diff
        diff = arr[i+1]-arr[i];
        
        // Calculate the current_sum
        if (curr_sum > 0)
            curr_sum = curr_sum + diff;
        else
            curr_sum = diff;
            
        // Update maxdifference, if needed
        maxDifference = max(maxDifference, curr_sum );
    }
    return maxDifference;
}

int main()
{
    int arr[] = {2, 5, 4, 10, 4, 9};
    //size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Maximum difference : " << max_diff(arr, n);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time Complexity Analysis

The time complexity is O(n), as iterating over a loop of size n results in an O(n) complexity.

Space complexity Analysis

We don't use any auxiliary space, the space complexity is O(1).

Frequently Asked Questions

How do you simply find the maximum difference between two elements in an array?

Make use of two loops. Pick elements one by one in the outer loop, then compute the difference between the picked element and every other element in the array in the inner loop and compare it to the maximum difference determined so far.
 

How is dynamic programming helpful?

Dynamic Programming is a technique that helps to efficiently solve problems that have overlapping subproblems and optimal substructure properties.
 

What is the asymptotic complexity of finding an array element based on an index?

It is constant O(1).

Conclusion

This article extensively discussed the problem of finding the maximum difference between two elements such that the larger element appears after the smaller number. We discussed two approaches to solve the problem and implemented both approaches in C++ and discussed their complexities in both the cases.

We hope this blog has helped you enhance your knowledge regarding finding the maximum difference in an array.  Are you interested in reading/exploring additional articles about this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and Analysis, Book Allocation Problem, Sorting Based Problems, Number Theory, and Dynamic Programing to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, and many more! You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!