当前位置：网站首页>LeetCode HOT 100(买卖股票的最佳时机)

int maxProfit(int* prices, int pricesSize){
    //暴力破解 超时
   int max=0,sum=0;
    for(int i=0;i<pricesSize-1;i++)
    {
        for(int j=i+1;j<pricesSize;j++)
        {
            sum=prices[j]-prices[i];
            max=fmax(max,sum);
        }
    }
    return max;
}

一次遍历求解(贪心法求解):

遍历一次数组:时间复杂度O(n)

有限个变量:空间复杂度O(1)

解题思路:

1、先判断今天是不是从开始到现在的历史最低点
2、如果不是最低点，那么如果今天卖股票的话，获利是不是最多的？
最后找出获利最多的结果就行了

关键点:

1：因为严格按照时间的先后顺序执行，一定要先买，在卖
2：遍历数组维护两个变量maxProfit最大的利润和minPrice最小价格。
3：如果当前价格小于最小的值minPrice时，更新minPrice的值。
4：当前前价格与最小值minPrice得差值大于maxProfi时，更细maxProfi的值
5：返回maxProfit的值

代码示例:

int maxProfit(int* prices, int pricesSize)
{

    int maxprofit=0;//最大利润
    int min=prices[0];//假设谷底为第一个数
    for(int i=1;i<pricesSize;i++)
    {
      if(prices[i]>min)
        {   //如果后面的的前面的大，求差比较利润
            maxprofit=fmax(maxprofit,prices[i]-min);
        }
        else if(prices[i]<min)//如果后面的比前面的小，后面替换前面当做谷底
        min=prices[i];
        //代替语句
        //maxprofit=fmax(maxprofit,prices[i]-min);
        //min=fmin(min,prices[i]);
    }
    return maxprofit;

}

动态规划求解:

五部曲解题思路:

1.确定dp数组以及下标的含义
dp[i][1] 表示第i天持有股票所得最多现金
说明：其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]，这是一个负数。
dp[i][0] 表示第i天不持有股票所得最多现金
说明：“持有”不代表就是当天“买入”！也有可能是昨天或更早就买入了，今天保持持有的状态。

2.确定递推公式
如果第 i 天持有股票即dp[i][1]，可以由两个状态推出来
第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][1]
第 i 天买入股票（第 i 天买入了也代表第 i 天持有股票），所得现金就是买入今天的股票后所得现金即： -prices[i]
那么dp[i][1]应该选所得现金最大的，所以dp[i][1] = max(dp[i - 1][1], -prices[i]);

如果第 i 天不持有股票即dp[i][0]，也可以由两个状态推出来
第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][0]
第 i 天卖出股票（第 i 天卖出了也代表第i天不持有股票），所得现金就是按照今天股票佳价格卖出后所得现金即： dp[i - 1][1] + prices[i]
同样dp[i][0]取最大的，dp[i][0] = max(dp[i - 1][0], prices[i] + dp[i - 1][1]);

3.dp数组初始化
那么dp[0][1]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][1] = -prices[0];
dp[0][0]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][0] = 0;

4.确定遍历顺序
从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。

5.返回值
因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多 dp[n-1][0];
如果不确定是哪个状态就取两个状态的最大值 max(dp[n-1][1], dp[n-1][0])

代码示例:

int maxProfit(int* prices, int pricesSize)
{
    //动态规划 dp[i][j] 表示第i天是否持有股票 j=1持有 j=0不持有
    int dp[pricesSize][2];
    dp[0][0]=0;
    dp[0][1]=-prices[0]; //定义数组，初始化边界
    for(int i=1;i<pricesSize;i++)
    {
        //第i天不持有股票;两种情况 昨天没有买，今天继续不买；昨天买了，今天卖了
        dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]+prices[i]);
        //第i天持有股票;两种情况 昨天买了，今天没卖;昨天没有买，今天买了
        dp[i][1]=fmax(dp[i-1][1],-prices[i]);
    }
    return dp[pricesSize-1][0];
}

感谢观看!后续持续更新LeetCode HOT 100题解

有兴趣可关注LeetCode 热题100专栏