• 优化后的代码如下

class Solution {
    public int maxProfit(int[] prices) {
        // 第0天股市结束后，如果手里有股票，那就是当前购买的，此时最大利润就是负数
        int prevWithStock = -prices[0];

        // 第0天股市结束后，如果手里没有股票，那就是没有购买过，此时最大利润只能等于0
        int prevWithoutStock = 0;

        // 当天股市结束后，如果手里有股票时的最大利润
        int currentWithStock;

        // 当天股市结束后，如果手里没有股票时的最大利润
        int currentWithoutStock = 0;
        
        for (int i=1;i<prices.length;i++) {
            currentWithoutStock = Math.max(prevWithoutStock, prevWithStock + prices[i]);
            currentWithStock = Math.max(prevWithStock, prevWithoutStock - prices[i]);
            prevWithStock = currentWithStock;
            prevWithoutStock = currentWithoutStock;
        }

        // 第i天结束后，手里不持有股票的最大利润就是返回值
        return currentWithoutStock;
    }
}

• 再次提交，稍微提升了一点
  
• 至此，买卖股票的基本套路，以及状态转移方程设计思路和实现，咱们已经学习到了，接下来的文章中，都会基于这个思路去设置状态转移方程
• 当然了，此刻您应该还有个疑问：为何速度的排名如此之低？接下来咱们来看看落后的原因

为啥排名不高？

• 这道题本身也有一些特殊：除了动态规划，贪心算法也能解
• 以prices={1, 2, 3}为例，聪明的您应该看出来了，如果1买入，3卖出，得到的利润等于2，属于最大利润
• 题目有个约束：一天不能既买入又卖出，如果跳出这个约束，那就可以做到1买入2卖出，然后2买入3卖出，利润还是2！
• 至于能不能将3-1转化成(3-2)+(2-1)呢？当然可以，减去2再加上2，对原题的结果毫无影响，却可以改变代码流程，如下所示，每当买入卖出能赚钱时，就将插件累加起来，这样的计算中，相比前面的代码，每次循环中的计算量明显减少了

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length<2) {
            return 0;
        }

        int total = 0;

        for (int i=1;i<prices.length;i++) {

            if (prices[i]>prices[i-1]) {
                total += prices[i] - prices[i-1];
            }

        }

        return total;
    }
}

• 再次提交，这回超越了百分百
  
• 至此又得出一个结论：本题用动态规划做并没有错，也不是动态规划代码没写好，而是有更高效的贪心算法恰巧也能解决此问题
• 经过本篇实战，相信您对动态规划以及股票买卖问题都有了更深的理解，接下来，继续挑战其他股票买卖问题，在LeetCode世界中向着股神前进

欢迎关注博客园：程序员欣宸

学习路上，你不孤单，欣宸原创一路相伴...