1. `121. 买卖股票的最佳时机`

在这里插入图片描述

1.1. 暴力遍历，两次遍历

1.1.1. 算法代码

public class Solution {
    public int MaxProfit(int[] prices) {
        int profitValue=0;

        for(int i=0;i<prices.Length;i++)
        {
            for(int j=i+1;j<prices.Length;j++)
            {
                if(prices[j]>prices[i])
                {
                    if(prices[j]-prices[i]>profitValue)
                    {
                        profitValue=prices[j]-prices[i];
                    }
                }
            }
        }
        return profitValue;
    }
}

上述代码的逻辑为两次遍历，后一个值比前一个值大，并使用哨兵变量profitValue记录最大差值。

1.1.2. 算法复杂度

时间复杂度： $O(n^2)=\frac {n*(n-1)}{2}$
空间复杂度： $O (1)$ ,因为只有哨兵变量profitValue

1.1.3. 算法问题

前面我们讲到，这个时间复杂度是 $O(n^2)$ ,是一个指数函数。

那么在数据非常大的时候，其根据时间复杂度可以知道，其复杂度非常的高，如leetcode的超时案例

[886,729,539,474,5,653,588,198,313,111,38,808,848,364,819,747,520,568,583,253,605,442,779,903,217,284,927,33,859,75,418,612,174,316,167,40,945,740,174,279,985,133,38,919,528,844,101,291,673,561,

.......
中间有3万个数值
.......

561,644,484,868,53,936,186,35,219,84,455,971,922,862,434,553,948,857,491,622,162,934,66,486,569,690,596,506,452,635,690]

其时间复杂度是： $30000 * 29999/2 = 449985000$ ,其计算数值大的可怕。

1.2. 一次遍历

1.2.1. 算法代码

public class Solution {
    public int MaxProfit(int[] prices) {
        int minprice = int.MaxValue;
        int maxprofit = 0;
        for (int i = 0; i < prices.Length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

其算法，基本思路是：在最低点购入，在最高点卖出,由于for循环是从0开始的，所以其每一次minprice是当前时点前最低点购入值，故此算法可靠

1.2.2. 算法复杂度

时间复杂度： $O (n)$
空间复杂度： $O (1) = 2$

2.2 122. 买卖股票的最佳时机 II

在这里插入图片描述

第一题相较比较简单，而第二题中增加了一个限定：可以购买多次，只是手上最多只有一支股票

2.1. 贪心算法

2.1.1. 算法代码

public class Solution {
    public int MaxProfit(int[] prices) {
        int ans = 0;
        int n = prices.Length;
        for (int i = 1; i < n; ++i) {
            int diffPrice=prices[i] - prices[i - 1];
            if(diffPrice>0)
            {
                ans += diffPrice;
            }
        }
        return ans;
    }
}

2.1.2. 算法思路与步骤

只要后一天的价格比今天高，那么我今天就买，后一天就卖。

在这里插入图片描述

2.1.3. 算法复杂度

时间复杂度： $O (n)$
空间复杂度： $O (1) = 2$

2.2. 动态规划算法

2.2.1. 算法代码

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length < 2) {
            return 0;
        }
        int[] OwnStocks=new int[prices.Length];
        int[] NoStocks=new int[prices.Length];

        OwnStocks[0]=-prices[0];
        NoStocks[0]=0;

        for(int i=1;i<prices.Length;i++)
        {
            OwnStocks[i]=Math.Max(OwnStocks[i-1],NoStocks[i-1]-prices[i]);
            NoStocks[i]=Math.Max(NoStocks[i-1],OwnStocks[i-1]+prices[i]);
        }

        return NoStocks[prices.Length-1];
    }
}

2.2.2. 算法思路与步骤

由于不可以同时存在多支股票，所以每天只有可能有两种状态有股票、没有股票
第一天存在股票=0-第一天股票价值；第一天不存在股票=0(没有购买或者当天售出)
后续每一天，当天有股票的最大利益=Math.Max(前一天有股票的值,前一天没有股票的值-当天股票值[购买股票])
后续每一天，当前没有股票的最大利益=Math.Max(前一天没有股票的值,前一天有股票的值+当天股票值[卖出股票]`)

图解如下：

在这里插入图片描述

2.2.3. 算法复杂度

时间复杂度： $O (n)$
空间复杂度： $O (n) = 2 n$

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

在这里插入图片描述

2.3.1. 动态规划算法

这一题就和第二题的动态规划类似，只是第二题是两个状态，而第三题是四个状态。

没有买入
第一次买入，没有卖出
第一次买出，没有卖入
第二次买入，没有卖出
第二次买出

由于没有买入全程是0所以不做考虑，列出了5种，但实际上只有4种状态。

2.3.2. 算法代码

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

        int oneBuy=-prices[0];
        int oneSale=0;
        int twoBuy=-prices[0];
        int twoSale=0;

        for(int i=1;i<prices.Length;i++)
        {
            oneBuy=Math.Max(oneBuy,-prices[i]);
            oneSale=Math.Max(oneSale,oneBuy+prices[i]);
            twoBuy=Math.Max(twoBuy,oneSale-prices[i]);
            twoSale=Math.Max(twoSale,twoBuy+prices[i]);
        }

        return twoSale;
    }
}