121. Best Time to Buy and Sell Stock

121

这个比较简单，大致思想：
1.如果sale-buy<=0，则该价格适合买入。
2.否则判断该价格卖出的价格是否最好。
代码如下：

    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int res = 0;
        int buy = prices[0];
        for(int i=1;i<prices.length;i++){
            if(prices[i]-buy<=0){
                buy=prices[i];
            }else{
                res = Math.max(res,prices[i]-buy);
            }
        }
        return res;
    }

122. Best Time to Buy and Sell Stock II

122

这道和上一道题的唯一区别就是允许多次买卖。总的策略就是买涨~~一直买买卖。
以下代码是我写的。

    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int res = 0;
        int buy = prices[0];
        for(int i=1;i<prices.length;i++){
            if(prices[i]-buy<=0){
                buy=prices[i];
            }else{
                res += prices[i]-buy;
                buy=prices[i];
            }
        }
        return res;
    }

当我看了官方的解释和代码后，真感觉自己智商被压制了。其实做算法题就是做数学题，关键是找到问题关键。下图就是关键。

image.png

123. 买卖股票的最佳时机 III

利用状态转移方程（动态规划）来解此题。

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[] dp = new int[5];
        /*
        j的5中状态
        j=0：不进行任何操作
        j=1：第一次买入
        j=2：第一次卖出
        j=3：第二次买入
        j=4：第二次卖出
         */
        dp[1] = -prices[0];
        dp[3] = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++) {
            //以下计算为主逻辑，可以考虑将dp声明为一位数组~~
            dp[1] = Math.max(dp[1], -prices[i]);
            dp[2] = Math.max(dp[2], prices[i] + dp[1]);
            dp[3] = Math.max(dp[3], dp[2]-prices[i]);
            dp[4] = Math.max(dp[4], prices[i] + dp[3]);
        }
        return Math.max(0, Math.max(dp[4], dp[2]));
    }

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems