最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

基础算法题:月饼的最佳买卖时机

XAMPP案例 admin 63浏览 0评论
大家好,我是牛牛,中秋节快到了,今天就来分享一道和月饼有关的基础算法题,提前祝大家中秋快乐!
01
故事起源

中秋节快到了,牛牛买了几盒公司月饼,过了几天,再打开内网一看,月饼的价格已经从公司的发售价78,涨到了150。短短几天,就翻了倍,这勾起了牛牛的好奇心,开始关注月饼价格。

盯了两天,发现价格每天都有波动,牛牛算是明白了,这鹅厂的月饼也变成了抢手货,有黄牛在中间捣腾,作为一个合格的程序员,当然联想到了自己的业务——这要是放在计算机里,黄牛的最佳买入卖出时机如何实现?

02
输入输出
我们以月饼每天的售价为输入,输出最大利润:

drf061

输入
[7,1,5,3,6,4]
输出
5
上例中,黄牛在第1天(月饼价格=1)的时候买入,在第4天(月饼价格=6)的时候卖出,可以获得最大利润=6-1=5。
03
花式炒饼

老规矩,我们还是由简入难,看看有哪些方法解决这个问题。

暴力法

简单来说,我们可以找到每一天和它之前天的差值,其中,差值最大的一组就是我们的最佳买卖时机。
在实际运行中,我们需要把每种可能性都算出来,最后找到差值最大的那组。

drf0061

func maxProfit(prices []int) int {
    var result int
    for i := 1; i < len(prices); i++ {
        for j := 0; j < i; j++ {
            result = max(result, prices[i] - prices[j])
        }
    }
    return result
}
这种方式虽然直截了当,但是时间复杂度是O(N^2),如果数据量比较多的时候,耗时会很长。在算法题中,可能会超时,一般只是作为基础解法,理清思路。

贪心算法

暴力法容易想到,但是效率太低。
想要利润最大,肯定是希望在最低点买入。我们就从一开始的时候,不断更新最低点,最低点和卖出点差值越大则利润越大。

drf00061

如图所示,从第0天开始,0是最低点,7块钱。到第1天,最低点只有1块钱,后续始终没有比1块钱更低的,所以第1天就是买入点。寻找到后续价格与第1天差值最大的那天,就是卖出点。

func maxProfit(prices []int) int {
    var minPrice = prices[0]
    var result int
    for i := 1; i < len(prices); i++ {
        minPrice = min(minPrice, prices[i])
        diff := prices[i] - minPrice
        result = max(result, diff)
    }
    return result
}

动态规划

我们刚才是以贪心的思路去看待问题,这道题用动态规划也是可以的。因为我们求解最佳的买卖点,其实可以看作最大递增子序列。
我们以数组dp表示以某天为卖点的最大获利。dp[i]的值取决于它前一天dp[i-1]和第i天的价格:假设如果第i天的价格减第i-1天的价格为diff,dp[i]就是dp[i-1] + diff,dp[i]不能为负,如果小于0,则令其等于0。

drf000061

func maxProfit(prices []int) int {
    var dp = make([]int, len(prices))
    var result int
    for i := 1; i < len(prices); i++ {
        diff := prices[i] - prices[i-1]
        dp[i] = max(dp[i-1] + diff, 0)
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}
04
月饼复盘
暴力法简单粗暴,心智成本低,但是执行效率也低。用它来帮助理清思路即可。
贪心算法符合生活常识,就像名字所说一样,求取当前的最值。最后的动态规划则是以迭代递推的思路解决问题。
这三种算法在算法题中都是非常常规和重要的,大多数算法题其实都可以用这三种思路去套,一开始我们可能不太熟悉,多多应用到不同题目,自然就会手到擒来了。
最后,祝大家都能在中秋吃到自己最喜欢的月饼!

价格。

盯了两天,发现价格每天都有波动,牛牛算是明白了,这鹅厂的月饼也变成了抢手货,有黄牛在中间捣腾,作为一个合格的程序员,当然联想到了自己的业务——这要是放在计算机里,黄牛的最佳买入卖出时机如何实现?

02
输入输出
我们以月饼每天的售价为输入,输出最大利润:

图片

输入
[7,1,5,3,6,4]
输出
5
上例中,黄牛在第1天(月饼价格=1)的时候买入,在第4天(月饼价格=6)的时候卖出,可以获得最大利润=6-1=5。
03
花式炒饼

老规矩,我们还是由简入难,看看有哪些方法解决这个问题。

暴力法

简单来说,我们可以找到每一天和它之前天的差值,其中,差值最大的一组就是我们的最佳买卖时机。
在实际运行中,我们需要把每种可能性都算出来,最后找到差值最大的那组。

图片

func maxProfit(prices []int) int {
    var result int
    for i := 1; i < len(prices); i++ {
        for j := 0; j < i; j++ {
            result = max(result, prices[i] - prices[j])
        }
    }
    return result
}
这种方式虽然直截了当,但是时间复杂度是O(N^2),如果数据量比较多的时候,耗时会很长。在算法题中,可能会超时,一般只是作为基础解法,理清思路。

贪心算法

暴力法容易想到,但是效率太低。
想要利润最大,肯定是希望在最低点买入。我们就从一开始的时候,不断更新最低点,最低点和卖出点差值越大则利润越大。

图片

如图所示,从第0天开始,0是最低点,7块钱。到第1天,最低点只有1块钱,后续始终没有比1块钱更低的,所以第1天就是买入点。寻找到后续价格与第1天差值最大的那天,就是卖出点。

 

func maxProfit(prices []int) int {
    var minPrice = prices[0]
    var result int
    for i := 1; i < len(prices); i++ {
        minPrice = min(minPrice, prices[i])
        diff := prices[i] - minPrice
        result = max(result, diff)
    }
    return result
}

动态规划

我们刚才是以贪心的思路去看待问题,这道题用动态规划也是可以的。因为我们求解最佳的买卖点,其实可以看作最大递增子序列。
我们以数组dp表示以某天为卖点的最大获利。dp[i]的值取决于它前一天dp[i-1]和第i天的价格:假设如果第i天的价格减第i-1天的价格为diff,dp[i]就是dp[i-1] + diff,dp[i]不能为负,如果小于0,则令其等于0。

图片

 

func maxProfit(prices []int) int {
    var dp = make([]int, len(prices))
    var result int
    for i := 1; i < len(prices); i++ {
        diff := prices[i] - prices[i-1]
        dp[i] = max(dp[i-1] + diff, 0)
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}
04
月饼复盘
暴力法简单粗暴,心智成本低,但是执行效率也低。用它来帮助理清思路即可。
贪心算法符合生活常识,就像名字所说一样,求取当前的最值。最后的动态规划则是以迭代递推的思路解决问题。
这三种算法在算法题中都是非常常规和重要的,大多数算法题其实都可以用这三种思路去套,一开始我们可能不太熟悉,多多应用到不同题目,自然就会手到擒来了。
最后,祝大家都能在中秋吃到自己最喜欢的月饼!

转载请注明:XAMPP中文组官网 » 基础算法题:月饼的最佳买卖时机