0121 买卖股票的最佳时机

简单 动态规划

算法思路

很显然的动态规划或贪心。遍历每一天的股价，假设在当天卖出，通过已经记录的股价最小值，计算出最大收益。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

代码实现

best-time-to-buy-and-sell-stock.c

#define max(a, b) ((b) > (a) ? (b) : (a))
#define min(a, b) ((b) < (a) ? (b) : (a))

int maxProfit(int* prices, int pricesSize) {
    int maxProfit = 0, minPrice = prices[0];
    for (int i = 1; i < pricesSize; i++) {
        minPrice = min(minPrice, prices[i]);
        maxProfit = max(maxProfit, prices[i] - minPrice);
    }
    return maxProfit;
}