Leetcode.121.Best Time to Buy an

题目

给定一个数组, 表示第i天的股票价格, 最多只能进行一次买卖, 如何获取最大利润.

Input: [7,1,5,3,6,4]
Output: 5
Input: [7,6,4,3,1]
Output: 0

思路1

循环
时间复杂度O(n²)

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

    return res;
}

思路2

在遍历时, 记录最小值, 然后遍历时的值减去最小值就可能得出最大值.
时间复杂度O(n)

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

总结

将题目转换为数学问题.