买卖股票的最佳时机(合集)

买卖股票的最佳时机I

买卖股票的最佳时机1

显而易见是贪心算法，遍历每天的股价，同时记录当前股价之前，最低的股价。那么比较当前股价与之前的最低股价：

最低股价 > 当前股价：说明股价下跌了，不能卖出；更新最低股价；

最低股价 < 当前股价：可以计算卖出的最大值，并且更新；

int maxProfit(vector<int>& prices) {
    int ans = 0;
    int min_price = prices[0];
    // 贪心算法
    // 假设第i天卖出股票，那么需要知道前 i-1天中，最低的股价，然后更新最大利润
    for (int i = 1; i < prices.size(); i++) {
        if (min_price > prices[i]) { // 不能卖出
            min_price = min(min_price, prices[i]);
        } else {
            ans = max(ans, prices[i] - min_price);
        }
    }
    return ans;
}

买卖股票的最佳时机II

买卖股票的最佳时机2

int maxProfit(vector<int>& prices) {
    // 1. 初始化最大利润为0，没有交易时利润就是0
    int ans = 0;
    // 2. 记录上一个价格（初始为第一天的价格，作为第一次可能的买入价）
    int last_price = prices[0];
    // 3. 从第二天开始遍历所有价格（因为要对比前一天）
    for (int i = 1; i < prices.size(); i++) {
        // 4. 如果当前价格 > 上一个价格：说明能赚差价，立即卖出
        if (prices[i] > last_price) {
            // 累加这次的利润（当前价 - 上一个买入价）
            ans += prices[i] - last_price;
            // 更新上一个价格为当前价（相当于：卖出后，若后续还要买，就以当前价作为新的买入价）
            last_price = prices[i];
        } else {
            // 5. 如果当前价格 ≤ 上一个价格：说明此时卖出会亏/不赚，更新买入价为更低的当前价
            last_price = min(last_price, prices[i]);
        }
    }
    // 6. 返回累加的总利润
    return ans;
}

买卖股票的最佳时机III

买卖股票的最佳时机3

因为最多买卖两次，那么就可以考虑从左往右计算最大利润，和从右往左计算最大利润，然后把两个数据的最大利润相加即可计算出总的最大利润。

int maxProfit(vector<int>& prices) {
    int n = prices.size();

    vector<int> pre(n, 0);  // 正向计算利润
    vector<int> post(n, 0);  // 反向计算利润

    // // 计算从0到i之间，最大利润是多少
    // int min_price = prices[0];
    // for(int i = 1; i < n; i++) {
    //     pre[i] = max(pre[i-1], prices[i] - min_price);
    //     min_price = min(min_price, prices[i]);
    // }

    // // 计算从i到n-1之间，最大利润是多少
    // int max_price = prices[n-1];
    // for (int i = n-2; i >= 0; i--) {
    //     post[i] = max(max_price - prices[i], post[i+1]);
    //     max_price = max(max_price, prices[i]);
    // }

    // 合并
    int min_price = prices[0];
    int max_price = prices[n-1];
    for(int i = 1; i < n; i++) {
        pre[i] = max(pre[i-1], prices[i] - min_price);
        min_price = min(min_price, prices[i]);
        int j = n - i -1;
        post[j] = max(max_price - prices[j], post[j+1]);
        max_price = max(max_price, prices[j]);
    }

    int ans = 0;
    // 遍历计算
    for (int i = 0; i < n; i++) {
        ans = max(ans, pre[i] + post[i]);
    }

    return ans;
}