python每日一题【剑指 Offer 63. 股票的最大利润】

day19-2022.11.14

题目信息来源
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源：力扣（LeetCode）

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1
2
3
4
5
6
7
8

一个垃圾解法，超时了，也没有动态规划，动态规划：定义dp，找到转移方程，初始状态，返回值

class Solution:
    def maxProfit(self, prices) -> int:
        # 暴力遍历，超时了，可以考虑趋势判断
        in_list, out_list, max_idx, min_idx = [], [], 0, 0
        # 判断趋势的标记, 1为找向下的趋势，找买入的时机，0为找向上的趋势，找卖出的时间，收益应该是卖出-买入
        flag = 1
        for i in range(1, len(prices)):
            # 判断向下的趋势
            if flag==1:
                # 找到向下趋势的最小值
                if prices[i]<prices[min_idx]:min_idx = i
                # 向下的趋势被破坏，开始找向上的趋势，max_num=prices[i]
                else:
                    flag = 0
                    max_idx = i
                    in_list.append(min_idx)
            if flag==0:
                # 找到向上趋势的值
                if prices[i]>prices[max_idx]:max_idx = i
                # 向上的趋势被破坏，开始找向下的趋势
                else:
                    flag = 1
                    min_idx = i
                    out_list.append(max_idx)
        result = 0
        for i in out_list:
            for j in in_list:
                if i>j:result = max(result, prices[i]-prices[j])
                else:continue
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

题解：

我思路出了一些问题，以为动态规划的转移方程，$dp[i]$ 一般都会和 $dp[i-1]$ 有相关性继承，且计算 $dp[i]$ 一般只考虑 $prices[i]$，思维太僵化了，一定要分析题目，直到最大利润始终是，最大值减去前面的最小值，也就是
$$dp[i]=max(dp[j-1],prices[i]-min(prices[0:i-1]))$$
前面 $dp[j-1]$ 的记忆继承，保证最大值的传承，后面减去的是前面的最小值。之后再减少每次都要处理 $min(price[0:i-1])$ 的时间复杂度，用一个变量保存前面的最小值，又因为最后输出只需要 $dp[i]$ ，用一个变量保存 $dp$，减少空间复杂。

class Solution:
    def maxProfit(self, prices) -> int:
        if not prices:return 0
        cost = prices[0]
        profit = 0
        for i in range(1, len(prices)):
            profit = max(profit, prices[i]-cost)
            cost = min(prices[i], cost)
        return profit
1
2
3
4
5
6
7
8
9

我的失败版本，呜呜呜，不是很甘心，改到这个版本，发现我的方法会遗忘最小数，当然最后的测试也过不了

class Solution:
    def maxProfit(self, prices) -> int:
        # dp[i]为当时卖出的利润
        dp = 0
        for i in range(1, len(prices)):
            if prices[i]-prices[i-1]>0:
                if dp==0:
                    dp = prices[i]-prices[i-1]
                    max_num = prices[i]
                    min_num = prices[i-1]
                elif dp==prices[i]-prices[i-1] and min_num>prices[i-1]:
                    min_num, max_num = prices[i-1], prices[i]
                else:
                    cross = min_num-prices[i-1]+prices[i]-max_num
                    add_sum = prices[i]-max_num
                    if cross>add_sum and cross>0:
                        dp = dp + cross
                        min_num, max_num = prices[i-1], prices[i]
                    elif add_sum>cross and add_sum>0:
                        dp = dp + add_sum
                        max_num = prices[i]
        return dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22