Leetcode 121 Solution

This article provides solution to leetcode question 121 (best-time-to-buy-and-sell-stock)
Categories:
Tags:
Access this page by simply typing in "lcs 121" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

Solution

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (prices.size() == 0)
            return 0;

        vector<int> a(n);
        for (int i = 0; i < n; i++)
            a[i] = i == 0 ? prices[i] : min(a[i - 1], prices[i]);

        int max_gain = 0;
        for (int i = 0; i < prices.size(); i++)
            max_gain = max(max_gain, prices[i] - a[i]);

        return max_gain;
    }
};