本篇文章小编给大家分享一下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个数字为结尾的子序列有两类 所以取较大的值即可
敢达决战官方正版 安卓版v6.7.9
下载敢达决战 安卓版v6.7.9
下载像素火影骨架佐助 (Perseverance Fire Shadow)手机版v1.16
下载要塞英雄 安卓版v33.20.0-39082670-Android
下载梦想城镇vivo最新版本 安卓版v12.0.1
梦想城镇vivo版是这款卡通风模拟经营类手游的渠道服版本,玩
怦然心动的瞬间 安卓版v1.0
怦然心动的瞬间是一款真人向的恋爱互动游戏,在游戏中玩家将扮演
曼尼汉堡店游戏 安卓版v1.0.3
曼尼汉堡店是一款非常好玩的精品恐怖类型冒险游戏,在这款游戏中
现代总统模拟器去广告版 安卓版v1.0.46
现代总统模拟器是一款休闲养成类游戏,可能对于不少的玩家来说都
现代总统模拟器付费完整版 安卓版v1.0.46
现代总统模拟器高级版在商店是需要付费的,相对于普通版本,高级