LeetCode 121。买卖股票的最佳时机#主旨：因为只能交易一只股票，所以可以列举必须以i位置作为卖出时机的情况下，得到的最大收益是多少。如果我们得到每个i位置的最大收益，那么最大收益必是所有位置的最大收益的最大值.
使用两个变量：
Min变量：指示遍历位置之前的最小值。
最大变量：指示在我当前收集的头寸上必须卖出的最大收入。
再次遍历数组。当遍历到I位置时，最小值和最大值的更新逻辑如下：
min=Math.min(arr，min)；//每次比较遍历的arr和全局min，看min max=Math.max(arr-min，max)的值是否可以刷新；//arr-min表示在I位置必须卖出时的最大利润是多少，全局最大值pk的最大值给max遍历数组。返回的max的值就是最终答案。查看完整代码：
public class leet code _ 0121 _ BestTimeToBuyAndSellStock { public int max profit(int arr){ int max=0；int min=arr0for(int I=1；长度；i ) { min=Math.min(arr，min)；max=Math.max(arr - min，max)；}返回max}}LeetCode 122。买卖股票的最佳时机二#主要思路：由于你可以交易任意次数，但任何时候你最多只能持有一只股票，我们可以捕捉股票曲线的所有上升段，累计收益就是最大收益。遍历数组，从遍历的位置中减去前一个位置的值。如果是阳性，就收藏。如果是负数，将当前收益设置为0(相当于不做这笔交易)，这样就可以遍历一次数组，不会错过所有收益。
设置一个变量max，初始值为0，以收集最大返回值。对于I位置，最大更新逻辑如下：
max=Math.max((prices - prices)，0)；完整的代码如下：
public int max profit(int prices){ int max=0；for(int I=1；一.价格.长度；I) {//抓所有上坡。max=Math.max((prices-prices)，0)；}返回max}从这个问题可以得出一个简单的结论：如果数组元素个数为N，则最多执行N/2次交易就可以抓取所有的上升段的值（极端情况下，当前时刻买，下一个时刻卖，保持这样的交易一直到最后，执行的交易次数就是N/2）.
LeetCode 188。买卖股票的最佳时机IV#主要观点：
如果k的值大于或等于数组长度的一半，则意味着有无限个事务。在这种情况下，可以直接使用问题2的解决方案。如果k的值小于数组长度的一半，则需要单独考虑。在第二种情况下，我们定义
Int=new int，其中dp表示在0范围内交易j次的最大收益是多少.我.如果可以填写二维表dp，那么返回的dp值就是问题的关键答案。
在这个二维矩阵dp中，
第一行中的值表示数组0范围内几个交易的最大回报.0，很明显，都是0。
第一列的值表示在数组0的范围内交易0次获得的最大利润.一、很明显，都是0。
关于任何通用位置dp的值，
我们可以列举我的位置是否参与交易。如果I持仓不参与交易，那么dp=dp。如果我的位置参与交易，那么我的位置必须是最后的销售机会。
最后一次购买的时间可以如下：
最后一次买入是在位置I，那么dp=dp-arr arr。
最后一次买入是在i-1位置，那么dp=dp-arr arr。
最后一次买入是在i-2位置，那么dp=dp-arr arr。
.
最后一次买入是在0位置，那么dp=dp0-arr0 arr
//i位置不参与交易，那么dp至少是dpdp=dpfor(int m=0；m=I；m ) {
// 枚举每次买入的时机 dppublic class LeetCode_0188_BestTimeToBuyAndSellStockIV { public static int maxProfit(int k, int<> arr) { if (arr == null || arr.length < 2) { return 0; } int N = arr.length; if (k >= N >> 1) { return infinityMax(arr); } int<><> dp = new int
dp
我们可以举一个具体的例子来说明如何优化，
比如，
当我们求dp<5><3>这个值，我们可以枚举5位置是否参与交易，假设5位置不参与交易，那么dp<5><3> = dp<4><3>，假设5位置参与交易，那么5位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：
最后一次买入的时机在5位置，那么dp<5><3> = dp<5><2> - arr<5> + arr<5>
最后一次买入的时机在4位置，那么dp<5><3> = dp<4><2> - arr<4> + arr<5>
最后一次买入的时机在3位置，那么dp<5><3> = dp<3><2> - arr<3> + arr<5>
最后一次买入的时机在2位置，那么dp<5><3> = dp<2><2> - arr<2> + arr<5>
最后一次买入的时机在1位置，那么dp<5><3> = dp<1><2> - arr<1> + arr<5>
最后一次买入的时机在0位置，那么dp<5><3> = dp<0><2> - arr<0> + arr<5>
我们求dp<4><3>这个值，我们可以枚举4位置是否参与交易，假设4位置不参与交易，那么dp<4><3> = dp<3><3>，假设4位置参与交易，那么4位置一定是最后一次的卖出时机。那最后一次买入的时机，可以是如下情况：
最后一次买入的时机在4位置，那么dp<4><3> = dp<4><2> - arr<4> + arr<4>
最后一次买入的时机在3位置，那么dp<4><3> = dp<3><2> - arr<3> + arr<4>
最后一次买入的时机在2位置，那么dp<4><3> = dp<2><2> - arr<2> + arr<4>
最后一次买入的时机在1位置，那么dp<4><3> = dp<1><2> - arr<1> + arr<4>
最后一次买入的时机在0位置，那么dp<4><3> = dp<0><2> - arr<0> + arr<4>
比较dp<5><3>和dp<4><3>的依赖关系，可以得到如下结论：
假设在求dp<4><3>的过程中，以下递推式的最大值我们可以得到
dp<4><2> - arr<4>
dp<3><2> - arr<3>
dp<2><2> - arr<2>
dp<1><2> - arr<1>
dp<0><2> - arr<0>
我们把以上式子的最大值定义为best，那么
dp<5><3> = Math.max(dp<4><3>,Math.max(dp<5><2> - arr<5> + arr<5>, best + arr<5>))
所以dp<5><3>可以由dp<4><3>加速得到，
同理，
dp<4><3>可以通过dp<3><3>加速得到，
dp<3><3>可以通过dp<2><3>加速得到，
dp<2><3>可以通过dp<1><3>加速得到，
dp<1><3>可以很简单得出，dp<1><3>有如下几种可能性:
可能性1，1位置完全不参与，则
int p1 = dp<0><3>可能性2，1位置作为最后一次的卖出时机，买入时机是1位置
int p2 = dp<1><2> + arr<1> - arr<1>可能性3，1位置作为最后一次的卖出时机，买入时机是0位置
int p3 = dp<0><2> + arr<1> - arr<0>此时，best的值为
int best = Math.max(p2 - arr<1>, p3 - arr<1>)然后通过dp<1><3>加速dp<2><3>，通过dp<2><3>加速dp<3><3>......，所以二维dp的填写方式是按列填，
先填dp<1><0>，dp<1><2>一直到dp<1>
然后填dp<2><0>,dp<2><1>一直到dp<2>
...
依次填好每一列，直到填完第N-1列。
枚举行为被优化，优化枚举后的完整代码如下：
public class LeetCode_0188_BestTimeToBuyAndSellStockIV { public static int maxProfit(int k, int<> arr) { if (arr == null || arr.length < 2) { return 0; } int N = arr.length; if (k >= N >> 1) { return infinityMax(arr); } int<><> dp = new int
LeetCode 309. 最佳买卖股票时机含冷冻期#主要思路：因为有了冷冻期，所以每个位置的状态有如下三种：
冷冻期持有股票不持有股票，不在冷冻期定义三个数组，分别表示i位置这三种情况下的最大值是多少
// 处于冷冻期int<> cooldown = new int
// 0位置需要处于冷冻期，说明0位置买了又卖掉，收益是0cooldown<0> = 0; // 0位置需要持有股票，只有可能在0位置买了一股，这个时候收益为0-arr<0>withStock<0> = -arr<0>;// 0位置没有股票，也不在冷冻期，说明在0位置就没有做任何决策。此时收益也是0noStock<0> = 0;针对一个普遍位置i
// 如果i位置要处于冷冻期，那么前一个位置必须持有股票，且在当前位置卖掉，处于cooldown状态cooldown = withStock + arr;// 如果i位置要持有股票，那么前一个位置可以持有股票，到当前位置不做决策，或者前一个位置没有股票，当前位置买入一股withStock = Math.max(withStock, noStock - arr);// 如果i位置没有股票，那么前一个位置可能也没股票，或者前一个位置是冷冻期，到当前位置也没有进行买入动作noStock = Math.max(noStock, cooldown);最大收益就是如上三种方式的最大值。完整代码见：
public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown { public static int maxProfit(int<> arr) { if (arr.length < 2) { return 0; } int N = arr.length; // 处于冷冻期 int<> cooldown = new int
public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown { // 空间压缩版本 public static int maxProfit(int<> arr) { if (arr.length < 2) { return 0; } // 处于冷冻期 int cooldown = 0; // 持有股票 int withStock = -arr<0>; // 不持有股票，也不处于冷冻期 int noStock = 0; for (int i = 1; i < arr.length; i++) { int next1 = Math.max(withStock, noStock - arr); int next2 = withStock + arr; int next3 = Math.max(noStock, cooldown); withStock = next1; cooldown = next2; noStock = next3; } return Math.max(cooldown, Math.max(withStock, noStock)); }}LeetCode 714. 买卖股票的最佳时机含手续费#主要思路：由于没有冷冻期，所以在i位置的时候，状态只有两种
// withStock表示：i位置有股票的状态下，最大收益int<> withStock = new int
// 0位置持有股票，最大收益，只可能是0位置买入一股withStock<0> = -arr<0>;// 0位置不持有股票，最大收益，只能是0位置不做交易，收益为0，如果0位置做交易，收益就是(0 - arr + arr - fee),显然小于0noStock<0> = 0;针对普遍位置i
// i位置需要有股票，说明i位置的股票可以是i-1位置到现在不交易获得的，也可以是i-1位置没有股票，买下当前这一股获得的withStock = Math.max(withStock, noStock - arr);// i位置没有股票，说明i位置的股票可以由i-1位置上有股票的状态到当前位置卖出一股（含手续费），也可以是沿用上一个位置没有股票的最大收益noStock = Math.max(withStock + arr - fee, noStock);完整代码如下：
public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee { public static int maxProfit1(int<> arr, int fee) { if (arr.length < 2) { return 0; } int<> withStock = new int
public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee { public static int maxProfit(int<> arr, int fee) { if (arr.length < 2) { return 0; } // 持有股票 int withStock = -arr<0>; // 不持有股票 int noStock = 0; for (int i = 1; i < arr.length; i++) { int next1 = Math.max(withStock, noStock - arr); int next3 = Math.max(withStock + arr - fee, noStock); withStock = next1; noStock = next3; } return Math.max(withStock, noStock); }}
原文链接：买卖股票的最佳时机系列问题 - Grey Zeng - 博客园
