蓝桥杯Python 最大连续区间和[动态规划]

简介: 蓝桥杯Python 最大连续区间和[动态规划]

be前言:期末临近,恰好明天考Python,今天就有时间做题了,希望对大家有帮助....(周五考完就可以全面备战蓝桥杯了= =)

问题描述:给定一段长度为N的整数序列A,请从中选出一段连续的子序列(可以为0)使得这段的总和最大



image.png

这里就不提暴力法了,只能在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个数字为结尾的子序列有两类 所以取较大的值即可

代码核心就是递推关系 上面已经给出证明 欢迎向我提出问题!我是小郑  

目录
相关文章
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2
|
5月前
|
存储 算法 数据挖掘
LeetCode第十六题: 掌握双指针技巧 最接近的三数之和 【python】
LeetCode第十六题: 掌握双指针技巧 最接近的三数之和 【python】
|
5月前
|
存储 算法 数据挖掘
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
LeetCode 题目 43:字符串相乘 多种算法分析对比 【python】
|
存储 人工智能 Python
逆序对-树状数组or暴力-python
逆序对-树状数组or暴力-python
72 0
|
Python
Python|动态规划之最大子序和
Python|动态规划之最大子序和
98 0
|
算法 Python
Python|贪心算法解最大子序和
Python|贪心算法解最大子序和
71 0
|
Python
蓝桥杯Python 最大连续区间和[动态规划]
蓝桥杯Python 最大连续区间和[动态规划]
110 0
蓝桥杯Python 最大连续区间和[动态规划]
|
算法 Python
[动态规划]Leetcode53.最大子序和(python)
[动态规划]Leetcode53.最大子序和(python)
|
算法 Python
[动态规划]Leetcode64.最小路径和(python)
[动态规划]Leetcode64.最小路径和(python)
[动态规划]Leetcode64.最小路径和(python)
|
Python
LeeCode-最长回文子串(python)三种解法
LeeCode-最长回文子串(python)三种解法
240 0