#include <iostream>
#include <vector>


using namespace std;

int maxProfit(vector<int> &prices) {
    size_t size = prices.size();
    
    if (size <= 1) {
        return 0;
    }
    
    /* opt: optimal
     * cur: current
     * buy: index in vector when buy
     * sell: index in vector when sell
     */
    int optProfit = 0;
    int optBuy = 0;
    int optSell = 0;
    int curBuy = 0;
    int curSell = 0;
    
    
    while (++curSell < size) {
        if (prices[curBuy] > prices[curSell]) {
            curBuy = curSell;
        } else if (prices[curBuy] < prices[curSell]) {
            if (optProfit < (prices[curSell] - prices[curBuy])) {
                optProfit = prices[curSell] - prices[curBuy];
                optBuy = curBuy;
                optSell = curSell;
            }
        }
    }
    
    return optProfit;
}