Java 中股票买卖利润最大化

这是技术面试中常问的突出问题之一。在此问题中，会给出一个表示不同日期股票成本的整数数组。请注意，一个人可以多次买卖股票。在本节中，我们将讨论 **Java 中股票买卖的最大化利润问题**。让我们来理解一下这个问题。

考虑以下数组。

int arr[] = {50, 90, 130, 155, 20, 267, 347}

在这里，第一天的股票成本是 50。第二天，成本变为 90，第三天变为 130，依此类推。因此，一个人可以在第一天购买股票，并在第四天卖出。因此，利润为 155 - 50 = 105。再次，可以在第五天购买股票，并在第七天卖出。因此，利润为 347 - 20 = 327，总利润为 105 + 327 = 432，这是赚取的最高利润。

方法：朴素

在这种方法中，会购买一只股票，然后每天在有利可图时将其卖出。此外，还需要跟踪迄今为止赚取的最高利润。以下程序对此进行了说明。

文件名： MaxProfitStock.java

输出

The price of the stock on different days is: 
50 90 130 155 20 267 347 
The maximum profit earned is: 432

方法：高效

为了使解决方案更高效，我们将不使用递归。在这种方法中，我们将寻找局部最小值和最大值。局部最小值将被视为起始索引，局部最大值将被视为结束索引。如果局部最小值不存在，则返回。我们还将通过更新买卖对的数量来更新解决方案。观察以下代码。

文件名： MaxProfitStock1.java

输出

The price of the stock on different days is: 
50 90 130 155 20 267 347 

Buy the stock on day: 1	 Sell the stock on day: 4
Buy the stock on day: 5	 Sell the stock on day: 7
Thus, the total profit is: 432

复杂度分析：外循环运行到 j = 0 到 size - 1。两个内循环在每次迭代中都会增加 j 的值。因此，这两个内循环有助于 j 更快地达到 size - 1。因此，程序的 time complexity 为 O(size)。程序还使用一些额外的空间来存储买卖股票的日期。因此，程序的 space complexity 为 O(size)，因为天数不能超过数组中存在的元素数量。

方法：波谷波峰

在这种方法中，我们需要查找下一个更大的元素并将其从当前元素中减去。我们这样做是因为除非达到最小值，否则差值会持续增加。请注意，我们没有使用任何额外的空间。此方法的时间复杂度仍为 O(size)。

以下 Java 程序对此进行了说明。

文件名： MaxProfitStock2.java

输出

The price of the stock on different days is: 
50 90 130 155 20 267 347 
The maximum profit earned is: 432

注意 1：如果股票价格按降序排列。那么，就无法赚取利润。

例如

int p[] = { 800, 795, 505, 440, 311, 261, 181, 101, 40, 5};

股票成本每天都在下降。因此，如果一个人在某一天购买了股票，那么在购买股票后的任何一天，股票的成本都会低于购买成本。因此，他会遭受损失。

注意 2：这个问题可以有很多变种。其中一个变种是在只允许买卖一次股票的情况下最大化利润。现在，这个问题类似于找到两个元素之间的最大差值，其中较大的值出现在较小的值之后。

如果我们取连续几天的股票价格 int p[] = {50, 90, 130, 155, 20, 267, 347}，那么一次买卖的最大利润是 347 - 20 = 327。

文件名： MaxProfitStock3.java

输出

The price of the stock on different days is: 
50 90 130 155 20 267 347 
The maximum profit earned is: 327

类似地，可以编写代码来最大化允许最多两次、或最多三次买卖股票的利润，依此类推。