• 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

Stock Buy Sell to Maximize Profit

April 18, 2015 by Dhaval Dave

Stock Price on each day is given in an array.
Example : [ 10, 12, 7, 5, 9, 15, 13, 18 ] Find the max profit that you can make by buying and selling in those days.
max profit is when u buy on 5 sell on 15, buy on 13 and sell on 18.

If 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 > index_Min, as we are allowed to buy and sell it more times.

Strategy : Start from 0th day, get Stock at minimum price (by comparing it with next day price). and Sell as soon as we get profit.
{ this is called finding local minima and maxima } 

Following is algorithm for this problem.
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as ending index.
If we reach the end, set the end as ending index.
3. Update the solution (Increment count of buy sell pairs)
4. Repeat the above steps if end is not reached.

Now along with it, w’ll store its indexes in our solution to calculate prices.

#include <stdio.h>
struct Interval{
//This structure to store results in local mim and max
 int buy;
 int sell;
};
 
void stockBuySell(int price[], int n)
{
 if (n < 1)
 return;
 
 int countSol = 0; 
 //count of total solutions
 
 Interval solution[n/2 + 1]; //sol
 // solution vector
 int i = 0;
 while (i < n-1)
 {
 // Find Local Minima.
 while ((i < n-1) && (price[i+1] <= price[i]))
 i++;
 
 // If we reached the end, break as no further solution possible
 if (i == n-1)
 break;
 
 // Store the index of minima
 solution[countSol].buy = i++;
 
 // Find Local Maxima.
 while ((i < n) && (price[i] >= price[i-1]))
 i++;
 
 // Store the index of maxima
 solution[countSol].sell = i-1;
 
 // Increment count of buy/sell pairs
 countSol++;
 }
 
 int totalProfit=0;
 //Calculate total Profit
 
 if (countSol == 0)
 printf("Sorry NO Profit Possibe\n");
 else
 {
 for (int i = 0; i < countSol; i++){
 totalProfit += price[solution[i].sell]-price[solution[i].buy];
 printf("Buy on day: %d\t Sell on day: %d Profit %d : \n", solution[i].buy, solution[i].sell, price[solution[i].sell]-price[solution[i].buy] );
 }
 printf("Total Profit %d",totalProfit);
 }
 
 return;
}
int main()
{
 int price[] = {2, 9, 10, 50, 47, 500, 100000};
 int n = sizeof(price)/sizeof(price[0]);
 stockBuySell(price, n);
 return 0;
}

You can send us mail on admin@gohired.in for queries and more interesting questions and solutions.
Find us on FACEBook :
GoHired Page  Gohired Group

Similar Articles

Filed Under: Amazon Interview Question, Hacker Earth Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array

Reader Interactions

Comments

  1. Ankit says

    July 26, 2015 at 6:08 am

    Can you explain why this solution would work?
    I am not getting the solution.

  2. Dhaval Dave says

    September 23, 2015 at 2:41 pm

    AS we can buy and sell maximum time, we should find min price to buy and max price to sell for first time, and same process to follow for rest of price
    ex : [ 10, 12, 7, 5, 9, 15, 13, 18 ]
    Find the max profit that you can make by buying and selling in those days.
    max profit is when u buy on 5 sell on 15, buy on 13 and sell on 18.
    so we are finding local min and local max.. see algorithm, hope it helps

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

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

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

Generate next palindrome number

Doubly linked list

Stickler thief

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Given Set of words or A String find whether chain is possible from these words or not

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Add Sub Multiply very large number stored as string

Wrong Directions given find minimum moves so that he can reach to the destination

C++ OOPs Part1

Get Minimum element in O(1) from input numbers or Stack

Count Possible Decodings of a given Digit Sequence

Reversal of LinkedList

Diagonal Traversal of Binary Tree

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Trapping Rain Water

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Generic Object Oriented Stack with Template

Find Nearest Minimum number in left side in O(n)

Connect n ropes with minimum cost

System Design: Designing a LLD for Hotel Booking

Difference between a LinkedList and a Binary Search Tree BST

BlueStone E-commerce Interview Experience

Check Binary Tree is Binary Search Tree or not

flattens 2 D linked list to a single sorted link list

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Find two non repeating elements in an array of repeating elements

Find next greater number with same set of digits

Flipkart Set 1 On Campus with Answers

Copyright © 2025 · Genesis Framework · WordPress · Log in