• 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

flattens 2 D linked list to a single sorted link list

VMWare Openings

Find min element in Sorted Rotated Array (Without Duplicates)

Possible sizes of bus to carry n groups of friends

Binary Tree Isomorphic to each other

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Sort Stack in place

CodeChef’ RRCOPY

Stickler thief

Given a string, find the first character which is non-repetitive

Level order traversal in Spiral form

The Magic HackerEarth Nirvana solutions Hiring Challenge

Right view of Binary tree

Cisco Hiring Event 21st – 22nd Feb 2015

Advanced SQL Injection

Diagonal Traversal of Binary Tree

LeetCode: Container With Most Water

SAP Off Campus Hiring_ March 2015 Verbal Skills

Python Dictionaries

Maximum path sum between two leaves

The greedy coins game Dynamic Programming

Sort an array according to the order defined by another array

Find Percentage of Words matching in Two Strings

Password Predictor

Add Sub Multiply very large number stored as string

Memory Efficient LinkedList

Circular Linked List

Find and print longest consecutive number sequence in a given sequence in O(n)

Trapping Rain Water

Find the kth number with prime factors 3, 5 and 7

Copyright © 2026 · Genesis Framework · WordPress · Log in