python求最大连续子数组的和
作者:7749ha 发布时间:2022-05-12 07:23:24
标签:python,最大连续,子数组,和
抛出问题:
求一数组如 l = [0, 1, 2, 3, -4, 5, -6],求该数组的最大连续子数组的和 如结果为[0,1,2,3,-4,5] 的和为7
问题分析:
这个问题很简单,直接暴力法,上代码。
# -*- coding:utf-8 -*-
# 日期:2018/6/9 7:46
# Author:小鼠标
# 最大连续子数组的和
l = [0, 1, 2, 3, -4, 5, -6]
# 暴力求解
def violence(l = []):
maxVal = 0
x,y=0,0
for i in range(0,len(l)+1):
for j in range(0,len(l)+1):
res = sum(l[i:j])
if res > maxVal:
maxVal = res
x = i
y = j
return maxVal,x,y
maxVal, x, y = violence(l)
print(maxVal,(x,y))
分治法:
关键是暴力法的时间复杂度太高,所以就在原有的基础上做了进一步的提升--分治法。
所谓分治法就是将原有的列表一分为二,那么最大的子列表只有三种情况:
1、最大子列表完全在左边
2、最大子列表完全在右边
3、最大子列表跨立在中间
所以我们分情况讨论,求出答案。这种方法一定程度的降低了时间复杂度,从之前的n^2降到了(n/2)^2 + 2n
# -*- coding:utf-8 -*-
# 日期:2018/6/9 7:46
# Author:小鼠标
# 最大连续子数组的和
l = [0, 1, 2, 3, -4, 5, -6]
#暴力求解
def violence(l = []):
maxVal = 0
x,y=0,0
for i in range(0,len(l)+1):
for j in range(0,len(l)+1):
res = sum(l[i:j])
if res > maxVal:
maxVal = res
x = i
y = j
return maxVal,x,y
#分治法 想左扫 向右扫,求出两边的最大值
def left_or_right(l):
maxVal = 0
term = 0
for i in l:
term += i
if maxVal < term:
maxVal = term
return maxVal
def Separate():
middle = int(len(l)/2)
l1 = l[0:middle]
l2 = l[middle:len(l)]
#左半部分
maxVal1,x1,y1 = violence(l1)
#右半部分
maxVal2,x2,y2 = violence(l2)
#跨立在中间
max_right = left_or_right(l2)
max_left = left_or_right(l1[::-1])
maxVal3 = max_right + max_left
return max(maxVal1,maxVal2,maxVal3)
val = Separate()
print(val)
动态规划:
即便是分治法,时间复杂度还是太高,不满足生产的需求,所以如果说只求最大子序列的和的值而不去追求最大子序列本身,我们又引出一个方法--动态规划
这种方法的时间复杂是是线性的,极大的降低了。
# -*- coding:utf-8 -*-
# 日期:2018/6/9 8:38
# Author:小鼠标
def function(lists):
max_sum = lists[0]
pre_sum = 0
for i in lists:
# 因为最大子列表一定是从一个非0的数开始的(假定列表中有正数有负数)
# 所以就可以暂时筛选调小于0的数,即便列表全是负数,那么最大的子列表肯定是负数最大的一个
if pre_sum < 0:
pre_sum = i
else:
pre_sum += i
if pre_sum > max_sum:
max_sum = pre_sum
return max_sum
lists = [0, 1, 2, 3, -4, 5, -6]
print(function(lists))
来源:https://www.cnblogs.com/7749ha/p/9162194.html
0
投稿
猜你喜欢
- 自定义模板标签,过滤器。英文翻译是Customtemplatetagsandfilters。customfilter自定义过滤器今天不在我的
- def get_seed_data(filename):dom = minidom.parse(filename)root = dom.do
- PDOStatement::getAttributePDOStatement::getAttribute — 检索一个语句属性(PHP 5
- 一、中间键的引入:Django中间件(Middleware)是一个 轻量级、底层的 “插件”系 统,可以介入 Django的请求和响应处理过
- 刚刚接触爬虫,基础的东西得时时回顾才行,这么全面的帖子无论如何也得厚着脸皮转过来啊!什么是 Urllib 库?urllib 库 是 Pyth
- 本文实例讲述了python读写配置文件操作。分享给大家供大家参考,具体如下:在用编译型语言写程序的时候,很多时候用到配置文件,作为一个约定的
- 本文实例讲述了python 协程中的迭代器,生成器原理及应用。分享给大家供大家参考,具体如下:1.迭代器理解迭代器:迭代器是访问可迭代对象的
- 背景尽管到目前为止HTML4和XHTML1仍能够很好地满足我们的要求,但是它们仍然存在不足。为了满足用户丰富的基于Web应该程序的需要,达到
- 值类型和引用类型值类型:int、float、bool和string这些类型都属于值类型,使用这些类型的变量直接指向存在内存中的值,值类型的变
- 获取一组radio被选中项的值var item = $(’input[@name=items][@checke
- 1. 线程的概念线程,有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元。一个标准的线程由线程I
- 0 环境Python版本:3.6.8系统版本:macOS MojavePython Jupyter Notebook1 引言七月了,大家最近
- 有时在处理不规则数据时需要提取文本包含的时间日期。dateutil.parser模块可以统一日期字符串格式。datefinder模块可以在字
- 简介今天试着用ptyhon做了一个抓取网页内容,并生成word文档的功能,功能很简单,做一下记录以备以后用到。生成word用到了第三方组件p
- 我就废话不多说了,大家还是直接看代码吧!a1 = raw_input("please input a number")a
- 我们先从一个常见的Python编程错误开始说起,我已经见过非常多的程序员犯过这种错误了:def do_not_raise(user_defi
- 目的将一些小的字符串合并成一个大字符串,更多考虑的是性能方法 常见的方法有以下几种:1.使用+=操作符BigString=smal
- 对于软件来说,每一个新版本的推出都应该是一种进步,不可否认,阿里旺旺2008版相较于之前的版本的确是有很多的进步,但进步的同时却也有着比之前
- 事实上,当我们向文件导入某个模块时,导入的是
- 爬虫利器BeautifulSoup中find和find_all的使用方法二话不说,先上段HTML例子<html> &