max profit #max subarray sum is similar

/* max profit or biggest drop. one pass
max subarray sum -- is a similar problem, if you visualize original input as deltas and construct a level-array
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> delta{4,5,-6,4,1,-6,4,-1,3,-8,3,1,1,-1}; //delta values

template<typename T> ostream & operator<<(ostream & os, vector<T> const & v){
  for(int i=0; i<v.size(); ++i) os<<v[i]<<" ";
void biggestProfit(vector<int> const & v){
  int biggest=0,  /*low*/watermark=v[0];

  for(int i=1; i<v.size(); ++i){
        if (v[i]<watermark) watermark=v[i];
        else biggest = max(biggest, v[i]-watermark);
  cout<<biggest<<" = biggest; watermark = "<<watermark<<endl;
int main(){
  cout<<"delta: "<<delta;
  vector<int> level;
  for(int i=1; i<delta.size(); ++i){
        level.push_back( level[i-1]+delta[i] );
  cout<<"absolution level: "<<level;
  cout<<"max Profit: "; biggestProfit(level);
  cout<<"... which is also the max subarray sum in the original Delta array !\n\n";

  cout<<"max Drop: ";
  reverse(level.begin(), level.end()); biggestProfit(level);

  cout<<"\nAll solved usint the same maxProfit algorithm\n";

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