Post date: Jun 29, 2013 2:45:45 AM
Problem
Assume you daily prices of a stock
3 7 4 10 11 8 5 4 8 yadda yadda
You can only buy 1 share or sell 1 share a day, but you can only sell if you own the stock.
You can't hold more than 1 share. write me an algo that finds me the strategy that has the highest pay off.
Don't want the generate all possible strategies and compare.
Solution
Buy Low, Sell High
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the strategy that has the highest pay off
Created Date : 29-Jun-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int FindHightestPayOffStrategy(int* arr, int len)
{
int buy(-1);
int i(0);
int profit(0);
for(i = 0; i < len - 1; i++){
if(buy == -1 && arr[i] < arr[i + 1]){
buy = arr[i];
cout << "Buy stock at " << i;
cout << " th day with price: " << arr[i] << endl;
}
if(buy != -1 && arr[i] > arr[i + 1]){
profit += (arr[i] - buy);
cout << "Sell stock at " << i ;
cout << "th day with price: " << arr[i] << endl;
buy = -1;
}
}
if(buy != -1 && arr[i - 1] < arr[i]){
profit += (arr[i] - buy);
cout << "Sell stock at " << i ;
cout << "th day with price: " << arr[i] << endl;
}
return profit;
}
int main(int argc, char* argv[])
{
int arr[] = {3, 7, 4, 10, 11, 8, 5, 4, 8 };
cout << "The stock curve is " << endl;
copy(arr, arr + sizeof(arr) /sizeof(arr[0]), ostream_iterator<int>(cout, " "));
cout << endl;
int profit = FindHightestPayOffStrategy(arr, sizeof(arr)/sizeof(arr[0]));
cout << "The profit is " << profit << endl;
cout << " ----------------------------" << endl;
int arr1[] = {3, 7, 14, 15, 17, 28, 35, 44, 48 };
cout << "The stock curve is " << endl;
copy(arr1, arr1 + sizeof(arr) /sizeof(arr[0]), ostream_iterator<int>(cout, " "));
cout << endl;
profit = FindHightestPayOffStrategy(arr1, sizeof(arr)/sizeof(arr[0]));
cout << "The profit is " << profit << endl;
cout << " ----------------------------" << endl;
int arr2[] = {133, 117, 114, 95, 77, 48, 35, 24, 18 };
cout << "The stock curve is " << endl;
copy(arr2, arr2 + sizeof(arr) /sizeof(arr[0]), ostream_iterator<int>(cout, " "));
cout << endl;
profit = FindHightestPayOffStrategy(arr2, sizeof(arr)/sizeof(arr[0]));
cout << "The profit is " << profit << endl;
return 0;
}
Output
The stock curve is
3 7 4 10 11 8 5 4 8
Buy stock at 0 th day with price: 3
Sell stock at 1th day with price: 7
Buy stock at 2 th day with price: 4
Sell stock at 4th day with price: 11
Buy stock at 7 th day with price: 4
Sell stock at 8th day with price: 8
The profit is 15
----------------------------
The stock curve is
3 7 14 15 17 28 35 44 48
Buy stock at 0 th day with price: 3
Sell stock at 8th day with price: 48
The profit is 45
----------------------------
The stock curve is
133 117 114 95 77 48 35 24 18
The profit is 0
Press any key to continue . . .