• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Maximum difference between two elements s.t larger element appears after the smaller number

April 15, 2015 by Dhaval Dave

Find maximum profit if you can buy & sell share just once.

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

Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9).
This difference can be the largest profit if shares are allowed to buy and sell once.

so in simple words 
we need to find A[i] and A[j] such that A[i] < A[j] and i< j

Think what can be done to achieve that.

[2, 3, 10, 6, 4, 8, 1] in this wee nedd to find 2 and 10. 
[2, 3, 10, 1, 4, 8, 11] thn in this it should be 1 and 11.
so as we read array from index 0 to N, we can find max_number later.
but we need to keep track of minimum number.

We can keep track of 
1) minimum number , min_num found so far
2) maximum difference, max_dif  found so far.

now if for next element in array , current diff ( A [ j ] - min_num ) is larger than existing then update max diff. 
and if A[ j ] is smaller then min_num update it.

code 

#include<stdio.h>
 
int maxDiff(int a[], int length)
{
 int max_diff = a[1] - a[0];
 int min_element = a[0];
 for( int i = 1 ; i < length ; i++ )
 { 
 if(a[i] - min_num > max_diff) 
 max_diff = a[i] - min_num;
 if(a[i] < min_num)
 min_num = a[i]; 
 }
 return max_diff;
} 

int main()
{
 int a[] = {1, 2, 6, 80, 100};
 int len = sizeof(a)/sizeof(a[0]);
 printf("Maximum difference is %d", maxDiff(a, len));
 return 0;
}

 

 

Similar Articles

Filed Under: Adobe Interview Questions, Amazon Interview Question, Interview Experience, Microsoft Interview Questions, problem Tagged With: Array

Reader Interactions

Trackbacks

  1. Stock Buy Sell to Maximize Profit | GoHired says:
    April 18, 2015 at 7:52 pm

    […] you can just buy and sell once thenn? -> you can think for Max and Min such that index_Max > index_Min. so this code is extension of Max and Min such that index_Max > […]

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find the smallest window in a string containing all characters of another string

Find Pythagorean Triplets in an array in O(N)

SAP Off Campus Hiring_ March 2015 Sample Questions

Templates in C++

Print Power Set of a Set

Test Cases for Round Function

VMWare SDEII Interview

Python String and numbers

Reliance Jio Software Developer Interview Experience

Memory Efficient LinkedList

Python Dictionaries

Printing Longest Common Subsequence

1014 Practice Question of New GRE – Princeton

LeetCode: Container With Most Water

Find if two rectangles overlap

Find position of the only set bit

Find min element in Sorted Rotated Array (With Duplicates)

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Generate next palindrome number

Skiing on Mountains Matrix

CodeChef’ RRCOPY

Find the element that appears once others appears thrice

BFS (Breath First Search)

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Practo Hiring Experience

flattens 2 D linked list to a single sorted link list

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Implement LRU Cache

Count Possible Decodings of a given Digit Sequence

Print all nodes that are at distance k from a leaf node

Copyright © 2026 · Genesis Framework · WordPress · Log in