您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【算法设计与分析】 最大子段和(动态规划)

【算法设计与分析】 最大子段和(动态规划)

【问题描述】
使用动态规划算法解最大子段和问题,具体来说就是,依据递归式,按照顺序求得子问题。

【输入形式】
在屏幕上输入一个序列元素,包含负整数、0和正整数。

【输出形式】
序列的最大子段和,及得到最大子段和时的起始和终止编号。

【样例输入】

-2 11 -4 13 -5 -2

【样例输出】

20
2
4

【样例说明】
输入:6个数,元素间以空格分隔。
输出:序列的最大子段和20,得到最大子段和时的起始编号为2,终止编号为4。

【题解代码】

C++代码暂不发布

Python代码:

a=[0]+[int(i) for i in input().split(" ")]
n=len(a)-1
ans,temp,left,right,tl,tr=0,0,0,0,0,0
for i in range(1,n+1):
    if temp>0:
        temp+=a[i]
        tr=i
    else:
        temp=a[i]
        tl=tr=i
    if temp>ans:
        ans=temp
        left=tl
        right=tr
print(ans,left,right,sep="\n")

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进