LeetCode算法题：买卖股票的最佳时机---python

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题：买卖股票的最佳时机---python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2176字，纯文字阅读大概需要4分钟。

内容图文

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
算法思路：动态规划算法（递归、非递归），暴力求解法，具体思路见下图：
单独编写了一个动态规划递归方式的demo：

arr = [7,6,4,3,1]
def rec_opt(arr, i):
    if i == 0:
        return 0
    elif i == 1 and arr[1] >= arr[0]:
        return arr[1] - arr[0]
    elif i == 1 and arr[1] < arr[0]:
        return 0
    else:
        A = arr[i] - min(arr[:i])
        B = rec_opt(arr, i-1)
        return max(A, B)

rec_opt(arr, len(arr)-1)
返回：0

LeetCode题中实现的代码：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 动态规划算法，递归，超出时间限制
        # def rec_opt(arr, i):
        #     if i == 0:
        #         return 0
        #     elif i == 1 and arr[i] >= arr[i-1]:
        #         return arr[i] - arr[i-1]
        #     elif i == 1 and arr[i] < arr[i-1]:
        #         return 0
        #     else:
        #         A = arr[i] - min(arr[:i])
        #         B = rec_opt(arr, i-1)
        #         return max(A, B)
        
        # 动态规划算法，非递归
        min_p, max_p = float("inf"), 0
        for i in range(len(prices)):
            min_p = min(min_p, prices[i])
            max_p = max(max_p, prices[i] - min_p)
        return max_p
    
        # # 暴力求解，找出两个之间的最大差值，但是超出时间限制
        # maxprofit = 0
        # for i in range(len(prices)):
        #     for j in range(i+1, len(prices)):
        #         profit = prices[j] - prices[i]
        #         if profit > maxprofit:
        #             maxprofit = profit
        # return maxprofit

动态规划的算法主要思路是：将一个大的最优问题转化为多个最优子问题，如上题中的最大收益问题，求前5天（总共5天的话）的最大收益，可以转换为前4天的最大收益–>前3天的最大收益–>前2两天的最大收益…这是一种递归的方式，由f(5)–>f(4)–>f(3)–>f(2)–>f(1)–>f(0)，然后由f(0)返过来作用前面的，思路很简单，但是太费时间，非递归的方式是，先求f(0)记录最大收益，再求f(1)并与f(0)比较，记录最大值，一次遍历即可完成。

动态规划的算法非常有趣，在求最优问题上非常方便，推荐大家看一下这个视频入门：动态规划（第二讲）

内容总结

以上是互联网集市为您收集整理的LeetCode算法题：买卖股票的最佳时机---python全部内容，希望文章能够帮你解决LeetCode算法题：买卖股票的最佳时机---python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---