买卖股票两次

Question

我正在努力理解这个 problem，我需要在允许我最多 buy/sell 股票两次时找出最大利润。提供的解决方案讨论了从左到右维护价格差异数组，这对我来说很有意义。然而，post 还谈到了维护另一个从右到左的价差数组，我无法理解为什么在第一笔交易后会获利的逻辑。

Prices= [1, 4, 5, 7, 6, 3, 2, 9]
left  = [0, 3, 4, 6, 6, 6, 6, 8]
right = [8, 7, 7, 7, 7, 7, 7, 0]
max_profit = 13

Answer 1

您提到的建议解决方案中有两个数组的事实与只允许使用 2 个事务的问题的约束有关。

同样规定，交易不应该被插入——即一个交易应该在另一个交易之前（在左边）另一个（将在右边） .

更具体地说，所提出的解决方案中的两个数组表示如下：

left[i] = 在区间[0,i]内买入卖出能做出的最佳交易。如果在时间 j 卖出（j 在 [0, i] 中），则应该在 0 到 j 的最低价处买入。
right[i] = 在区间[i,n-1]内买入卖出所能做出的最佳交易。如果在时间 j 买入（j 在 [i, n-1] 中），卖出应该以从 j 到 n-1 的最高价完成。

所有需要找到的是两个事务的良好分离点 i。那么最佳组合将涉及利润 left[i] + right[i]，这可以通过尝试所有可能的 i 值来找到。

Answer 2

你可以像DP一样破解这个问题，首先设定你不买卖股票的情况，所以第一个利润为零，以同样的顺序赚取利润

当只有一笔交易时

跟踪数组并保持先前价格的最小值，最大利润是数组中的最大数-最小数。所以问题基本上是在一个数组中找到最大值和最小值，差异将是最大利润，这里我们只是更新利润数组，直到特定日期是否进行交易为止的最大利润。该数组将用作请求进一步交易中的数据使用。

// Condition for the only one transaction is possible
       for (int i = 1; i < n; i++) {
         min = Math.min(price[i - 1], min);
           profit[i] = Math.max(profit[i - 1], price[i] - min);
        }

如果最多可以进行两次交易

现在这里的事情很棘手，我们必须跟踪之前为获得最大利润所做的任何计算，直到 k-1 笔交易（这里 k=2）。对于任意数量的交易，该问题都可以成为动态问题。

profit for a particular day is = max{ if no transaction is made (Then previous max profit, ie profit[i - 1]),
previous_profit + Max of sale possible{present price - all previous price(i,i-1,...0))

对于 k=2

//   Condition for at most two transaction is possible
        for (int i = 1; i < n; i++) {
           max = Math.max(max, profit[i] - price[i]);
             profit[i] = Math.max(profit[i - 1], max + price[i]);
        }

这里是k笔交易的通用代码 我们只需要两个数组来跟踪以前的利润值并在每次迭代时覆盖。它也可以使用二维数组完成，但我们不需要任何以前的数据所以我用偶数和正数据数组

   package DynamicProblems;

    public class StockSales {

        private static int maxProfit(int price[], int n, int k) {
            int currentProfit[] = new int[n];
            int previousProfit[];
            int evenProfit[] = new int[n];
            int oddProfit[] = new int[n];

            for (int t = 0; t <= k - 1; t++) {
                int max = Integer.MIN_VALUE;
                if (t % 2 == 1) {
                    currentProfit = oddProfit;
                    previousProfit = evenProfit;
                } else {
                    currentProfit = evenProfit;
                    previousProfit = oddProfit;
                }

                for (int i = 1; i < n; i++) {
                    max = Math.max(max, previousProfit[i - 1] - price[i - 1]);
                    currentProfit[i] = Math.max(currentProfit[i - 1], max + price[i]);
                }
            }
            return currentProfit[n - 1];
        }

        public static void main(String args[]) {
            int price[] = {3, 4, 10, 103};
            int k = 1;
            int n = price.length;
            System.out.println("\nMaximum Profit = " + maxProfit(price, n, k));
        }
    }

买卖股票两次

Buy and Sell stocks twice

language-agnostic

algorithm

dynamic-programming