目标
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
说明：
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
思路
虽然这是一道简单题，但是我也想了一个多小时。算法实现起来简单，但是算法的设计，如何得到满足条件的结果也不是那么直观。
说回这道题，要求得最大利润，我们都明白要低买高卖。难道这道题就是让求数组的最大值与最小值？显然不是。我们的目标是求取一个买入点，再其之后的某天卖出获得的利润最大。只能操作一次，可以看成是长线交易（后面还有一道可以多次操作的题）。
暴力解法是遍历股票价格数组，然后向后循环，求得最大利润。时间复杂度是O(n!)，不可行。
思考下面的问题：
取得最大利润是否必须在最低点买入？不是，比如[2,8,1,6]。
取得最大利润是否必须在最高点卖出？不是，比如[3,8,1,7]。
但是，如果遇到了更低的价格，那么它一定是当前最佳的买入点。因为不管后续价格怎么波动，想要获得最大收益，被减数当然越小越好。
因此，问题可以转化为：任取一个买入点，向后遍历并记录最大利润，直到出现一个更低的买入点，在这之前的一段时间内，我们所选的就是最佳买入点，可以记录这段时间内的最大利润。然后以新的最佳买入点继续向后遍历并记录最大利润，直到一个新的最佳买入点出现。在这一过程中如果最大利润比之前的值更大就替换掉。这样我们就得到了问题的答案。
其实，一开始我并没有这么清晰的思路。只是跟着感觉走：
- 首先，如果遍历时发现股票价格是递减的，那么我们肯定不能买入。这里，我们需要计算后一天减去前一天的收益，如果连着都是负数，那么直接跳过。
- 然后，如果找到了第一个正收益的点，那么我们买入。之后，我们开始累加收益，这样累加得到的是当天到买入点的收益。即 如果a是我们的买入点，那么往后利润的累加和
profitSum为(b - a) + (c - b) + (d - c) + (e - d) = e - a。在这一过程中，我们记录最大收益profitMax。 - 接下来，我们需要找到更低的买入点。如果我们的买入点是i，当我们遍历到第j天的时候，
profitSum = prices[j] - prices[i]，而当天与前一天的利润为profit = prices[j] - prices[j-1]，如果profit > profitSum，那么prices[j] - prices[j-1] > prices[j] - prices[i]即prices[j-1] < prices[i]。j-1就是新的最佳买入点。这时我们需要将利润和重置，然后再比较最大利润。
最开始写的时候忽略了查找最新买入点的这个步骤，增加的这个判断 profit > profitSum 是根据错误案例调试出来的，感觉就是如果一天的收益就比之前的历史收益大了，那就没必要再累加前面的利润了，应该重新开始。
代码
/**
* @date 2024-03-03 1:44
*/
public class MaxProfit {
public int maxProfit(int[] prices) {
int profitSum = 0;
int profitMax = 0;
for (int i = 1; i < prices.length; i++) {
int profit = prices[i] - prices[i - 1];
if (profitSum <= 0 && profit <= 0) {
continue;
}
profitSum += profit;
if (profit > profitSum) {
// 最开始的时候没写这个判断
profitSum = profit;
}
if (profitSum > profitMax) {
profitMax = profitSum;
}
}
return profitMax;
}
public static void main(String[] args) {
MaxProfit main = new MaxProfit();
System.out.println(main.maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4}));
}
}
理清楚之后发现许多操作是没必要的，比如累加每天的利润，实际就是当天价格减去买入点价格。
public int maxProfit(int[] prices) {
int buyPoint = 0;
int profitMax = 0;
for (int i = 1; i < prices.length; i++) {
int profit = prices[i] - prices[buyPoint];
if (profit <= 0) {
buyPoint = i;
} else if (profit > profitMax) {
profitMax = profit;
}
}
return profitMax;
}性能
优化后
