Best Time to Buy and Sell Stock Solutions in C++

// Source : https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
// Author : Hao Chen
// Date   : 2014-06-18



class Solution {
public:
    //
    // This solution is O(1) space dynamic programming 
    //
    // We can make sure the max profit at least be ZERO. So,
    //    1) we have two pointers (begin & end ) 
    //    2) if prices[end] - prices[begin] >  0, then move the "end" pointer to next
    //    3) if prices[end] - prices[begin] <= 0, then move the "begin" pointer to current posstion.
    //    4) tracking the max profit
    //
    // Notes:
    //    Some people think find the highest-price & lowest-price, this is wrong. 
    //    Because the highest-price must be after lowest-price
    //
    int maxProfit(vector<int> &prices) {
        
        int max=0, begin=0, end=0, delta=0;
        
        for (int i=0; i<prices.size(); i++) {
            
            end = i;
            
            delta = prices[end] - prices[begin];
            
            if (delta <= 0){
                begin = i;
            }
            
            if ( delta > max ){
                max = delta;
            }
            
        }
        
        return max;
        
    }
};


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MAX;
        int profit = 0;
        for (auto p : prices) {
    	    // Keep tracking the previous lowest price
            buy = min (buy, p);
	    // Keep tacking the current max profit
            profit = max(profit, p - buy);
        }
        return profit;
    }
};

#include <vector>
#include <algorithm>
using std::vector; using std::max; using std::min;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int ret{0}, low{prices[0]};
        for (auto price : prices)
        {
            low = min(low, price);
            ret = max(ret, price - low);
        }
        return ret;
    }
};

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>
#include <vector>

using namespace std;

/// One Pass
/// for every price, find the max profit if we sell the stock here
/// we need to record the minimum buy price before every sell price
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        if(prices.size() == 0)
            return 0;

        int minPrice = prices[0];
        int res = 0;
        for(int i = 1 ; i < prices.size() ; i ++){
            res = max(res, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

        return res;
    }
};

int main() {

    int prices1[] = {7, 1, 5, 3, 6, 4};
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/ sizeof(int));
    cout << Solution().maxProfit(pricesVec1) << endl;

    int prices2[] = {7, 6, 4, 3, 1};
    vector<int> pricesVec2(prices2, prices2 + sizeof(prices2)/ sizeof(int));
    cout << Solution().maxProfit(pricesVec2) << endl;

    return 0;
}