Python最大连续区间和动态规划
作者：Py小郑? 发布时间：2023-02-13 09:40:32
标签：Python,连续区间,动态规划
be前言：期末临近，考Python的同学可以练练
问题描述：给定一段长度为N的整数序列A，请从中选出一段连续的子序列（可以为0）使得这段的总和最大
这里就不提暴力法了，只能在OJ系统里得10分（等于没写.........）下面呈现代码：
N=int(input().strip())
A=list(map(int,input().strip().split()))#输入格式
A.insert(0,0)#初始化
N+=1
dp=list(range(N))#dp[i]代表第i个数字结尾的序列最大值
dp[0]=0
if max(A)<=0:#如果全部是负数则不取 输出0
print(0)
else:
for i in range(1,N):
dp[i]=max(A[i],dp[i-1]+A[i])#下面细说
print(max(dp)) if max(dp)>0 else print(0)#如果最大子序列和小于0 那就干脆不取 0大于负数
#细说：、
#dp[i]表示第i个数字结尾的子序列最大值
#分析 设第i个数字为a[i] ①dp[i]=a[i]或
(设以a[i]结尾的区间序列和为s1,s2,s3...sn，所以dp[i-1]=max(s1,s2,....sn)
dp[i]=max(s1+a[i],s2+a[i]...sn+a[i])=a[i]+max(s1，s2..sn)
#即 ②dp[i]=a[i]+dp[i-1]
#故第i个数字为结尾的子序列有两类 所以取较大的值即可
来源：https://blog.csdn.net/m0_62277756/article/details/122416919
0
投稿猜你喜欢
- Microsoft Access 数据库 (.mdb) 文件大小2 G 字节。不
- 如果你想让你的IIS支持wml,做个wap网站,只需作小小的改变就行了.虽然目前支持wml的虚拟主机极少,但是自己在本机上玩玩也好的.首先在
用法示例：import random# 1）随机小数print(random.random()) # 获取大于0且小于1 之间的小数 &nb- 本文列举了所有关于PHP语言中使用socket相关服务的一些函数。注意使用如下函数之前，你需要确保你的socket已打开，如果你没有打开，请
- SQL Server数据库快捷键：书签：清除所有书签。 CTRL-SHIFT-F2书签：插入或删除书签（切换）。 CTRL+F2书签：移动到
- 本文实例讲述了Python只用40行代码编写的计算器。分享给大家供大家参考，具体如下：效果图：代码：from tkinter import
- 上次在“给网页添加打印按钮”一文中，有一段代码是“复制本文链接到剪贴板”js脚本，很可惜只能在IE中使用。这次在“淘宝网在线充值中心 - 荆
- 前言ThinkPHP出于安全的考虑增加了表单令牌Token，由于通过Ajax异步更新数据仅仅部分页面刷新数据，就导致了令牌Token不能得到
- win2000注册表程序 regedt32.exe下面是解决IIS出现Active Server Pages错误&
- Microsoft SQL Server 2000 能提供超大型系统所需的数据库服务。大型服务器可能有成千上万的用户同时连接到 SQL Se
- numpy 数组及运算扩展库 numpy 是 Python 支持科学计算的重要扩展库，是数据分析和科学计算领域如 scipy、pa
- 在网上有很多相关主题的讨论，但是一般都是用Iframe和XMLHTTP来实现。Iframe的实现可能是最常看到的。很多论坛和聊天室的无刷新效
- 1、确认框架中安装了第三方alibabacoud控件实现代码如下上传过程中遇到任务问题，可以进行留言<?php namespace A
- 为了防止某些别有用心的人从外部访问数据库，盗取数据库中的用户姓名、密码、信用卡号等其他重要信息，在我们创建数据库驱动的解决方案时，我们首先需
- Photoshop Express,也就是传说中的web版photoshop,来了。和想象中的web photoshop相比，这个Photo
- 本文实例讲述了PHP邮件发送类PHPMailer用法，并详细讲述了其具体的操作步骤。分享给大家供大家参考。具体步骤如下：1.在服务器安装 s
- 导读：由于banner一般用于专题类网站，在门户网站的二级页面，用户进来之前，在首页已经对主题有一定的了解和认识，所以banner的作用是在
- PHP crc32() 函数实例输出 crc32() 的结果：<?php $str = crc32("Hello World
- 通过视图来访问数据，其优点是非常明显的。如可以起到数据保密、保证数据的逻辑独立性、简化查询操作等等。但是，话说回来，SQL Server数据
- IE独有属性AlphaImageLoader用于修正7.0以下版本中显示PNG图片的半透明效果。这个滤镜的问题在于浏览器加载图片时它会终止内
