Problem
Given:You have given Amazon's stock prices for next 10 days
Find out: max benefit in best time complexity to buy and sell 1 share
Condition: Share must be sold any day after buying date.
For ex:
Share in thousands
5 1 4 6 7 8 4 3 7 9
Max benefit 9 - 1 = 8 thousand
Solution
I have to say the above example is not correct. The actual max benefit is 13.
First buy at second day(1) and sell at sixth day(8);
Second buy at the eighth day(3) and sell it at the tenth day(9).
So the total profit is 8- 1 + 9 - 3 = 13.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find max benefit in best time complexity
Created Date : 26-July-2013
Last Modified : 27-July-2013
===========================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
int MaxBenefit(int* arr, int len)
{
int mini = arr[0];
int maxi = arr[0];
int profit(0);
for(int i = 1; i < len; ++i){
if(arr[i] - arr[i - 1] > 0){
profit += arr[i] - arr[i - 1];
}
}
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 " << MaxBenefit(arr, len) << endl;
cout << "-------------------------" << endl;
}
int main(int argc, char* argv[])
{
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]));
return 0;
}
Output
The array is
5 1 4 6 7 9 4 3 5 3 7 8
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
Max benefit is 8
-------------------------
The array is
5
Max benefit is 0
-------------------------
Press any key to continue . . .