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个数字为结尾的子序列有两类 所以取较大的值即可

到此这篇关于Python最大连续区间和动态规划的文章就介绍到这了,更多相关Python最大连续区间和动态规划内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python实现最大子序和（分治+动态规划）

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和. 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6. 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解. 思路: 首先我们分析题目,我们思考,为什么最大和的连续子数组不包含其他的元素而是这几个呢?因为如果我们想在现有的基础上去扩展当前连续子数组,相邻的元素是一定要被加入的,而相邻

  • 浅析python实现动态规划背包问题

    一个包可以背4kg的东西,现在有四件东西,重量分别为1kg,4kg,3kg,1kg,价值为:1500,3000,2000,2000: 现在要求你,在包里背的东西价值最大,但是不能超过背包的最大载重量 #几件物品的重量 w = [0,1,4,3,1] #几件物品的价值 v= [0, 1500, 3000, 2000, 2000] #物品数量 n = len(w) - 1 #包的载重量 m = 4 #建立一个列表表示在包中的物品,元素是True时代表对应元素放入 x = [] #放入包中的总价值 v

  • Python动态规划实现虚拟机部署的算法思想

    Python动态规划实现虚拟机部署的算法思想

    声明 本文章为个人拙见,仅仅提供参考,不一定正确,各位大佬可以发表自己的意见. 题目描述 考虑到在虚拟机部署中资源提供商通常希望自己的收益最大化,现假设有一台宿主机,共有x个cpu和y GB的内存,用户可以采取自己报价的方式向资源提供商申请使用虚拟机资源,譬如说付w元申请a个cpu和b GB内存的一台虚拟机.请你设计一个算法,让资源提供商可以合理地安排虚拟机,使得自己的收益最大化. 输入: n x y 2 4 200 4 2 150 - 说明,n表示共有n条用户报价申请,宿主机共有x个cpu和y

  • python动态规划算法实例详解

    如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项 代码如下: #

  • Python最大连续区间和动态规划

    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个数字结尾的序列最大值

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • 动态规划之矩阵连乘问题Python实现方法

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125.

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • 分析python动态规划的递归、非递归实现

    概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

  • Python 剪绳子的多种思路实现(动态规划和贪心)

    剑指Offer(Python多种思路实现):剪绳子 面试14题: 题目:剪绳子 题:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,且n>1,m>1),每段绳子的长度记为k[0],k[1],k[2],...,k[m].请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积为18. 解题思路一:基于动态规划和贪婪算法. class Solution: def MaxProductAfterCut

随机推荐