max profit #max subarray sum is similar


/* max profit or biggest drop. one pass
max subarray sum -- is a similar problem, if you visualize the items as price changes
*/
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

template<typename T> void dump(vector<T> const & v){
	copy(v.begin(), v.end(), ostream_iterator<T>(cout, " "));
	cout<<endl;
}
int main(){
    vector<int> v={9,1,3,7,8,1,6,5}; //prices
	dump(v);

	// HighestProfit, LowestPx
	int hp=0, lpx=v[0];
	for (unsigned int i=1; i<v.size();++i){
		int aa=v[i];
		if (aa<lpx){
			lpx=aa;
			continue;
		}
		int profit = aa-lpx;
		if (profit > static_cast<int>(hp)){
			cout<<profit<<" > "<<hp<<endl;
			hp=profit;
		}
	}
	cout<<"ret = "<<hp;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s