[LeetCode] Buy and Sell Stock Series

这几个题目是leetcode的一个系列
best time to buy and sell stock

Say you have an array for which the ith element is the price of a given stock on day i.
design an algorithm to find the maximum profit

题目前提大概就是说你有一个数组, 存着i天的stock价格, 你要找到最大的价格差

买当然也必须在卖之前, 不能先卖后买

版本一, 只交易一次

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),

那就是有个最大值, 有个最小值, 每次用当天的价格stock[i]的减去此前最低价格就行了

然后对得到的差价求一个max就行

int maxProfit(vector<int> &prices) {
    int low = INT_MAX, profit = 0, maxp = 0;
    for(int i = 0; i < prices.size(); i++) {
        int profit = prices[i] - low;
        maxp = max(maxp, profit);
        low = min(low, prices[i]);
    }
    return maxp;
}

版本二, 随意交易

You may complete as many transactions as you like
(ie, buy one and sell one share of the stock multiple times).
However, you may not engage in multiple transactions at the same time
(ie, you must sell the stock before you buy again).

其实这个情况要比之前简单, 随意交易, 你可以注意一下坡峰坡谷, 假设是这样的情况

        ----
       /    \
   ---       -------
  /                 \
-
0 1   2    3 4     5 6

这个波动的山代表stock的价格, 你看这些价格, 你用2最高点减去0最低点是你的最大收益对吧, 但他其实是组合的
就是[0-1]段 和 [1-2]段的合并, 如果有下跌呢?


             ----
            /    \
    ---   --      -------
   /   \ /               \
 --     -
/
0 1 2 3 4 5 6  7 8      9 10

下跌不管就好了, 我们只要上升的差价, 这意味着只要有delta值大于0就行

int maxProfit(vector<int> &prices) {
    int total = 0;
    for (int i = 1; i < prices.size(); i++) {
        total += max(prices[i] - prices[i-1], 0);
    }
    return total;
}