53. Maximum Subarray@python
2024-08-29 19:00:26
Given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
题目地址: Maximum Subarray
难度: Easy
思路: 最大子序列和问题
代码:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
tmp = 0
res = float('-inf')
for i in range(n):
if tmp < 0:
tmp = 0
tmp = tmp + nums[i]
res = max(res, tmp)
return res
时间复杂度: O(n)
空间复杂度: O(1)
最新文章
- 常用的 SQL 函数
- git 使用笔记
- Bull And Cows
- OpenSSl编译
- php文件处理
- poj1528---(数论)
- C# 数据库连接测试以及备份
- Dubbo Zookeeper
- OGRE HelloWorld
- 关于scrapy的piplines
- neo4j语法
- Python内置函数(21)——filter
- 大数据平台Lambda架构详解
- About the Importance of Aim in Life
- webservice学习教程(二)--理论
- Spring 学习教程(一):浅谈对Spring IOC以及DI的理解
- dialog里屏蔽ESC和回车
- Git中特别的命令
- OSG和ProLand 的海面仿真
- (最全)Xpath、Beautiful Soup、Pyquery三种解析库解析html 功能概括
热门文章
- VMWare虚拟机Windows下的下载与安装
- 第九组 通信3班 063 OSPFv2与OSPFv3综合实验
- 03.Jquery Mobile中的按钮
- 网站前端开发--css篇
- MySql提示:The server quit without updating PID file(…)失败之解决办法(来源网络仅供参考)
- yii2.0下,JqPaginator与Pjax实现无刷新翻页
- 基于.NetCore2.1。服务类库采用.Net Standard2.0,兼容.net 4.6.1消息推送服务
- 爬虫(GET)——handler处理器和自定义opener
- LINUX中IPTABLES防火墙使用
- webpack.config.js====entry入口文件的配置