Problem
Given:You have given Amazon's stock prices for next 10 days
Find out: what is the best sell and buy time that makes max benefit in best time complexity.
buy and sell 1 share condition: Share must be sold any day after buying date.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the best sell and buy time that make max benefit
Created Date : 27-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
int BestBuySellTime(int* arr, int len)
{
int mini = arr[0];
int maxi = arr[0];
int profit(0);
bool bought(false);
for(int i = 1; i < len; ++i){
int delta = arr[i] - arr[i - 1];
if( delta > 0){
profit += delta;
if(!bought){
cout << "Buy at " << i - 1 << "th day " << endl;
bought = true;
}
}
else if(delta < 0){
if(bought){
cout << "Sell at " << i - 1 << "th day " << endl;
bought = false;
}
}
}
if(bought){
cout << "Sell at " << len - 1 << "th day " << endl;
}
return profit;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
cout << "Max benefit is " << BestBuySellTime(arr, len) << endl;
cout << "-------------------------" << endl;
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 20; ++i){
cout << setw(4) << i;
}
cout << endl;
int arr[] = {5, 1, 4, 6, 7, 9, 4, 3, 5, 3, 7, 8};
DoTest(arr, sizeof(arr) /sizeof(arr[0]));
int arr1[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1};
DoTest(arr1, sizeof(arr1) /sizeof(arr1[0]));
int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
DoTest(arr2, sizeof(arr2) /sizeof(arr2[0]));
int arr3[] = {5};
DoTest(arr3, sizeof(arr3) /sizeof(arr3[0]));
int arr4[] = {5, 1, 1, 4, 6, 7, 9, 9, 9, 4, 3, 3, 5, 5, 3, 7, 7, 8, 8};
DoTest(arr4, sizeof(arr4) /sizeof(arr4[0]));
return 0;
}
Output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
5 1 4 6 7 9 4 3 5 3 7 8
Buy at 1th day
Sell at 5th day
Buy at 7th day
Sell at 8th day
Buy at 9th day
Sell at 11th day
Max benefit is 15
-------------------------
The array is
9 8 7 6 5 4 3 2 1
Max benefit is 0
-------------------------
The array is
1 2 3 4 5 6 7 8 9
Buy at 0th day
Sell at 8th day
Max benefit is 8
-------------------------
The array is
5
Max benefit is 0
-------------------------
The array is
5 1 1 4 6 7 9 9 9 4 3 3 5 5 3 7 7 8 8
Buy at 2th day
Sell at 8th day
Buy at 11th day
Sell at 13th day
Buy at 14th day
Sell at 18th day
Max benefit is 15
-------------------------
Press any key to continue . . .