53最大子序和.py
2024-09-04 21:30:08
题目:给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
来源:https://leetcode-cn.com/problems/maximum-subarray/solution/
法一:动态规划
思路:关键是要正确的写出状态转移方程.dp[i]表示的是以nums[i]结尾的最大子串和,注意不是nums[i]中的最大子串和,如果是nums[i]中的最大子串和,则状态转移方程较复杂,无法直接写出.
参考:https://leetcode-cn.com/problems/maximum-subarray/solution/dong-tai-gui-hua-jie-fa-4xing-pythondai-ma-by-mcdu/
from typing import List
class Solution():
def maxSubArray(self, nums: List[int]) -> int:
dp=nums[:]
for i in range(1,len(nums)):
dp[i]=max(dp[i-1]+nums[i],nums[i])
return max(dp) if __name__ == '__main__':
duixiang = Solution()
a = duixiang.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
print(a)
法二:官方解法
class Solution:
def maxSubArray(self, nums: 'List[int]') -> 'int':
n = len(nums)
max_sum = nums[0]
for i in range(1, n):
# 如果前一个数大于0,则加到当前数上,
if nums[i - 1] > 0:
nums[i] += nums[i - 1]
# 否则是小于等于0,求该数与之前和的最大值.
max_sum = max(nums[i], max_sum)
return max_sum
yyy
最新文章
- CLR:基元类型、引用类型和值类型
- ZAM 3D 制作简单的3D字幕 流程(二)
- JavaScript-在当前显示区范围内实现点不到的小方块
- ios 向工程里添加Fonts
- zookeeper 3.4.6启动流程粗略梳理
- JAVA嵌套循环
- Hive常用的SQL命令操作
- webpack使用webpack-dev-middleware进行热重载
- 【转】android 电池(三):android电池系统
- usbmanger android 底下USB的工作模式
- [DeeplearningAI笔记]神经网络与深度学习人工智能行业大师访谈
- 部署testlink报错,安装wampserver时提示丢失MSVCR110.dll
- java多线程(8)---阻塞队列
- microsoft.jet.oledb.4.0 未注册
- Spring Boot Shiro 权限管理 【转】
- TableLayoutPanel 动态添加 行 列
- Postman Postman测试接口之POST提交本地文件数据
- Java异常(三) 《Java Puzzles》中关于异常的几个谜题
- IOS 设备备份文件详解 (一)
- 【angular5项目积累总结】遇到的一些问题以及解决办法