The Interview Question Today#16(11-3-19)

Question:

Given an array arr[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number.

Example:

Input : arr = {2, 3, 10, 6, 4, 8, 1}

Output : 8 (The maximum difference is between 10 and 2).

Solution:

Approach:

minElementTillNow will be initialise to arr[0].
Iterate over  arr[]
If current element is greater than minElementTillNow
calculate the difference.
If the difference is greater than maxDifference then update the maxDifference.
If current element is lesser than minElementTillNow
update minElementTillNow with current element.
We will get maxDifference in the end.

C program:

#include<stdio.h>

    // Create a diff array of size n-1. The array will hold

    //  the difference of adjacent elements

int maxDiff(int arr[], int n)

{

    int diff[n-1],i;

    for (i=0; i < n-1; i++)

        diff[i] = arr[i+1] - arr[i];

    int max_diff = diff[0];

    for (i=1; i<n-1; i++)

    {

        if (diff[i-1] > 0)

            diff[i] += diff[i-1];

        if (max_diff < diff[i])

            max_diff = diff[i];

    }

    return max_diff;

}

int main()

{

    int arr[100],i,n;

    printf("Enter The Number of Elements U Want to Insert ");

    scanf("%d",&n);

    printf("\nEnter the Elements\n");

    for(i=0;i<n;i++){

        scanf("%d",&arr[i]);

    }

    printf("Maximum difference is %d",  maxDiff(arr,n));

    return 0;

}

Output:

Enter The Number of Elements U Want to Insert 5

Enter the Elements

2

5

6

60

20

Maximum difference is 58