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]<<" ";
  os<<endl;
}
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;
  level.push_back(delta[0]);
  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";
}
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