Stock buy/sell, maximum subarray problem, C++ (gcc)

Stock buy/sell, maximum subarray problem

#include <iostream>
#include <vector>
#include <climits>

#include <stdio.h>

using namespace std;

Kadane's algorithm

// real max subarray
void maxSubArray(vector<int>& numbers) {

int max_so_far  = numbers[0], max_ending_here = numbers[0];
 
    int begin = 0;
    int begin_temp = 0;
    int end = 0;

for(int i = 1; i < numbers.size(); i++) {
    
        // calculate max_ending_here
        if(max_ending_here < 0) {
            max_ending_here = numbers[i];
            begin_temp = i;
        } else {
            max_ending_here += numbers[i];
        }
 
        // calculate max_so_far
        if(max_ending_here >= max_so_far ) {
            max_so_far  = max_ending_here;
 
            begin = begin_temp;
            end = i;
        }
    }
    
    
    cout << begin << " " << end << endl;
    cout << max_so_far << endl;
}

// stock numbers
void bestStockBuySell(vector<int>& t) {
 
    if (t.empty())
        return;
    
    
    int maxDiff = INT_MIN;
    
    int diff = 0;
    int lowest = t[0];
    
    int begin = 0;
    int end = 0;
    int tmpBegin = 0;
    
    
    for (int i = 0; i < t.size(); ++i) {

diff += t[i] - t[i - 1];

if (diff > maxDiff) {
            maxDiff = diff;
            begin = tmpBegin;
            end = i;
        }
        
        if (t[i] < lowest) {
            lowest = t[i];
            diff = 0;
            tmpBegin = i;
        }
 
    }
    
    cout << begin << " " << end << endl;
    cout << maxDiff << endl;
    
}

int main() {
 
    vector<int> t = { -111, 29, 12, 30, -30, -25, -20, -199};
    bestStockBuySell(t);
    maxSubArray(t);
 
}


run \| edit \| history \| help	0