本文共 1417 字，大约阅读时间需要 4 分钟。

问题分析：在股票交易中实现最大利润

想象一下，你有一个股票价格数组，其中每个元素代表某只股票在特定日期的价格。你的任务是设计一个算法，通过多次买卖股票，获取最大可能的利润。与传统的买卖股票问题不同，这里的交易有一些特定的限制条件：不能同时进行多次交易，且在卖完股票后，必须等待至少一天才能再次进行买入。

解决思路：引入状态变量

为应对这种限制条件，我们可以使用动态规划的方法来维护几个关键的状态变量：

通过遍历价格数组，我们可以根据这些状态变量来决定是否进行买入和卖出，从而最大化利润。

状态转移

每一步，我们都会根据前一次的状态来决定当前的操作：

代码实现：

int maxProfit(int[] prices) {    int preBuy = Integer.MIN_VALUE;    int buy = preBuy;    int preSell = 0;    int sell = 0;    for (int price : prices) {        preBuy = buy; // 上次可能的价格变成当前的买入状态        buy = Math.max(preSell - price, preBuy);        preSell = sell; // 上一次卖出的状态        sell = Math.max(buy + price, preSell);        // 如果当前的买入后的利润小于卖出后的利润，则保持不变    }    return sell;}

代码解释：

• preBuy：保持上一次的买入价格。
• buy：记录当前能买入的价格，或者是从等待状态下的最高价格减去当前价格后的价格。
• preSell：当前卖出后的价格。
• sell：记录当前卖出后的最高价格。

通过这种状态转移方式，我们可以确保在每一天尽可能地进行更多的交易，同时遵守等待一天的规则。

优化和考虑

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常适用于大型数据量的股票价格数组。

总结

通过引入buy、sell和rest这三个状态变量，我们可以有效地处理等待一天后再买入的情况，从而在有限交易次数的情况下实现最大收益。这种方法不仅逻辑清晰，而且能够高效地解决问题。