best-time-to-buy-and-sell-stock-ii

Best Time to Buy and Sell Stock II – LeetCode 122

Problem

Description

Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. 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).

Answer

Original

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int margin, total = 0;
        for(unsigned i = 0; i != prices.size() - 1; ++i){
            margin = max(prices[i+1] - prices[i],0);
            total += margin;
        }
        return total;
    }
};

思路

寻找一切的利差然后全部相加，连续的可以视为一次买入在最高点卖出，中断处看作下一笔交易的开始。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$74.13\%$

Better

思路

还没看到更好的解法。