Cinte's Leetcode Record
0%

121. Best Time to Buy and Sell Stock

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

121. Best Time to Buy and Sell Stock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for(size_t i = 0; i < prices.size(); ++i)
        {
            if(prices[i] < minPrice)
            {
                minPrice = prices[i];
            }
            if(prices[i] - minPrice > maxProfit )
            {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
};
Kadane’s Algorithm

所有的差就相当于前一天卖今天买，如果连续起来的话那就是i-1天买i天卖，i天买i+1天卖=i-1天买，i+1天卖。所以当到i时收益为负数时候。i之前的持有没有意义，我不如i天买，后面卖还有可能变正

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxCur = 0;
        int maxSoFar = 0;
        for(auto i = prices.begin() + 1; i != prices.end(); ++i )
        {
            maxCur = max(0, (*i - *(i-1)) + maxCur); // 当0 > 后面那个时候，肯定是负的了，而不买必定为0，所以利润至少为0
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
};
另一种思路
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN;
        int sell = 0;
        for(auto price : prices)
        {
            buy = max(buy, -price); // 使得购入的成本尽可能小，也就是负数尽可能大
            sell = max(sell, buy + price); // 使得卖出后的利润尽可能大
        }
        return sell;
    }
};