社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

每日一道算法题--leetcode 53--最大子序和--python

杉杉不要bug • 6 年前 • 566 次点击  
阅读 7

每日一道算法题--leetcode 53--最大子序和--python

【题目描述】

【代码思路】

一维动态规划问题,状态转移方程为:

dp[i]=max(nums[i],dp[i-1]+nums[i]) 【上代码】

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:return nums[0]
        dp=[]
        dp.append(nums[0])
        for i in range(1,len(nums)):
            dp.append(max(nums[i],nums[i]+dp[i-1]))
        return max(dp)
复制代码

看效果,时间复杂度线性:

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/33652
 
566 次点击