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, " "));
int main(){
    vector<int> v={9,1,3,7,8,1,6,5}; //prices

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

Leave a Reply

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

You are commenting using your 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