买卖股票两次

Question

我正在努力理解这个问题，当我被允许最多两次买卖股票时，我需要找出最大利润。所提供的解决方案涉及维护从左到右的价差数组，这对我来说是有意义的。然而，这篇文章也谈到了从右到左保持另一组价差的问题，我无法理解这种逻辑，因为这是为什么在第一笔交易之后才能获得利润。

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个事务的问题的约束有关。

如还规定的那样，不应插入事务--即一个事务应位于(左边)另一个事务(右边)之前。

更具体地说，所提议的解决方案中的两个数组代表以下内容：

• 如果买卖时间为j (j为0，i)，则应以0到j的最低价格进行买入。
• righti i=在i，n-1区间内买卖的最佳交易。如果购买时间为j(j在i，n-1中)，则应以从j到n-1的最高价格进行卖出。

所有需要找到的是一个好的分离点，我，两个事务。然后，最佳组合将涉及利润左撇子+权利，这可以通过尝试所有可能的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)) 

For 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));
        }
    }