interviewalgo
, , ,
Source
Edit
History

121. 买卖股票的最佳时机

Introduction

Question：121. 买卖股票的最佳时机

Analysis

非常简单的一道题，看上去是一道贪心的题目。

某一天的价格减去其之前所有价格的最小值即为在当天卖出时所能获得的最大收益。因此从前向后遍历整个数组，维护当前见过的最小值，这样就能求得每一天所能获得的最大收益，取个最大值即可。

Implement

1
2
3
4
5
6
7
8
int maxProfit(vector<int>& prices) {
    int res = 0, minPrices = INT_MAX;
    for(auto& p: prices) {
        minPrices = min(minPrices, p);
        res = max(res, p - minPrices);   
    }
    return res;
}

One More Thing

这道题是一个系列：