最多两次交易利润计算

Pensando en la estrategia

Estoy tratando de encontrar los máximos beneficios con hasta dos transacciones, evitando comprar simultáneamente. La solución se asemeja al problema "Best Time to Buy and Sell Stock III" de Leetcode.

Buscar maximó ganancias

Estoy viendo cómo resolver el problema de maximizar las ganancias con dos transacciones máximo. Estoy pensando en la programación dinámica, ya que dividir el array no es lo más eficiente.

Monitoreo del comportamiento

Estoy observando cómo cuatro variables clave están rastreando las transacciones. Compras y ventas deseadas se están midiendo, destacando posibles oportunidades de inversión.

Analizando la update

Estoy revisando cómo ajustar las variables con el estado dinámico (DP) para calcular la mejor ganancia, manteniendo un control eficiente de dos transacciones como máximo.

Estableciendo métricas

Establezco cuatro indicadores clave: ganancia máxima sin transacciones y sin acciones, ganancia máxima sin transacciones pero con una acción, ganancia máxima con una transacción y sin acciones, y ganancia máxima con una transacción y con una acción. Esto me da una base clara para evaluar la rentabilidad.

Manejando las variaciones

Estoy abordando estados de DP para representar maximización de beneficios con dos transacciones. Inicializa estados con precios negativos y actualiza cada estado dependiendo del movimiento de precios. ¡Curioso giro en la estrategia!

Maximizando ganancias

Estoy mapeando cómo maximizar las ganancias de dos acciones mediante programación dinámica, con una complejidad de tiempo de O(n) y espacio de O(1), siguiendo el enfoque de cuatro estados.

Ajustando valores de inicio

Estoy probando diferentes valores iniciales para s1 y s3 en el código Python, comenzando con -prices[0] pero ahora lo estoy ajustando a float('-inf') para verificar su precisión.

Evaluando métodos eficientes

要解决这个问题，我们需要设计一个算法，在最多允许进行两次交易的情况下，计算出可以获得的最大利润。

这是一个经典的股票交易问题，可以通过动态规划来解决。下面我将详细解释解决这个问题的思路和步骤。

思路分析：

由于最多只能进行两次交易，并且在再次购买之前必须卖掉之前的股票，我们可以将整个交易过程分为四个阶段：

第一次买入（buy1）：在最低价格买入第一次股票。
第一次卖出（sell1）：在最高价格卖出第一次股票，获得第一次交易的最大利润。
第二次买入（buy2）：在第一次卖出后的最低价格买入第二次股票。这里需要考虑已经获得的第一次交易的利润。
第二次卖出（sell2）：在最高价格卖出第二次股票，获得第二次交易的最大利润。

我们需要在遍历价格数组的过程中，不断更新这四个变量，以追踪在不同阶段的最大利润。

算法步骤：

初始化变量：
- buy1：在第一次买入时的最大利润（由于是支出，初始化为负无穷大）。
- sell1：完成第一次卖出后的最大利润（初始化为0）。
- buy2：在第二次买入时的最大利润（初始化为负无穷大）。
- sell2：完成第二次卖出后的最大利润（初始化为0）。
遍历价格数组，更新变量：

对于每天的价格price，执行以下更新：
- 更新buy1：
```
buy1 = max(buy1, -price)
```
  解释：选择更低的价格买入第一次股票，buy1取当前值和-price的最大值。
- 更新sell1：
```
sell1 = max(sell1, buy1 + price)
```
  解释：计算卖出第一次股票后的最大利润，sell1取当前值和buy1 + price的最大值。
- 更新buy2：
```
buy2 = max(buy2, sell1 - price)
```
  解释：在第一次交易的利润基础上，选择更低的价格买入第二次股票，buy2取当前值和sell1 - price的最大值。
- 更新sell2：
```
sell2 = max(sell2, buy2 + price)
```
  解释：计算卖出第二次股票后的最大利润，sell2取当前值和buy2 + price的最大值。
返回结果：

遍历完成后，sell2即为最多两次交易可以获得的最大利润。

代码实现：

def maxProfit(prices):
    if not prices:
        return 0

    buy1 = float('-inf')
    sell1 = 0
    buy2 = float('-inf')
    sell2 = 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2

解释：

buy1：在每一天，都尝试更新第一次买入的最大利润，即在更低的价格买入。
sell1：在每一天，都尝试更新第一次卖出的最大利润，即在当前价格卖出是否能获得更高的利润。
buy2：在每一天，都尝试更新第二次买入的最大利润，这里要减去当前价格，并加上第一次交易的利润sell1。
sell2：在每一天，都尝试更新第二次卖出的最大利润，即在当前价格卖出第二次股票是否能获得更高的总利润。

时间复杂度和空间复杂度：

时间复杂度：O(n)，其中n为价格数组的长度。我们只需遍历一次数组。
空间复杂度：O(1)，只使用了固定数量的变量。

总结：

通过动态规划的方法，我们将复杂的问题分解为多个阶段，并在每个阶段维护当前的最大利润。这个算法高效地解决了最多两次交易的股票买卖问题，具有线性的时间复杂度和常数级的空间复杂度。

最多两次交易利润计算

Pregunta

Pensamiento

Respuesta

Compartir este Q&A