这个题目有很多做法,在这里分享我的思路。

其实很明显这是个ACM题目,我是用贪心法分别求出正向每个位置之前最大子段和,反向某位置之后的最大子段和。

在判断的时候就是一个复杂度为n的匹配,即用max更新正向value1[i]+反向value2[i+1](注意题目条件是s1>=i&&s2>i)的最大值即可

分享我的代码:

#coding:utf-8
a=[-132,133,134,-11,12,-139,-140,62,63,-64,65,66,67,
    1,2,3,4,5,-6,7,-48,-49,50,138,16,17,20,
    101,102,-103,104,-105,106,146,147,148,-107,108,109,110,96,
    21,-22,23,-24,-25,25,-27,-28,-29,30,
    41,-42,8,9,10,-46,-47,
    51,52,-53,54,-55,-56,57,-58,59,60,
    73,-74,75,-71,-72,18,-97,-98,19,-129,130,
    -137,136,-13,14,144,-145,15,128,
    77,-78,-31,32,35,-76,149,-150,99,100,119,
    91,-92,-93,94,95,116,117,114,118,120,
    81,82,83,-84,85,-122,-123,
    112,111,-43,44,45,-113,-115,36,-37,-38,39,40,25,126,127,
    131,-135,61,-69,70,
    141,-142,143,-86,68,-87,-90,
    121,-88,89,-124,-179,-80,-33,34]
value1=[-99999]*150
value2=[-99999]*150
max=0
sum=0
for i in range(0,150):  #贪心计算正向每个位置,开头为a[0]
    sum+=a[i]
    if max<sum:
        max=sum
    value1[i]=max
    if sum<0:
        sum=0
max=0
sum=0
for i in range(149,-1,-1):
    sum+=a[i]
    if max<sum:
        max=sum
    value2[i]=max
    if sum<0:
        sum=0
max=0
for i in range(0,149):
    if(value1[i]+value2[i+1]>max):
        max=value1[i]+value2[i+1]
print max

Flag:

温馨提示: 此处内容需要评论本文后刷新才能查看,支付2元即可直接查看所有Flag。

小广告:关于获取西普实验吧所有Flag请点击这里查看索引

查看所有Flag文章需要输入密码,需要获取文章密码的童鞋请扫描下面微信或支付宝二维码捐助至少2元(老哥,捐多捐少是个缘分)之后发送支付凭证号联系我获取,Flag大全地址:Flag大全

新功能:捐款的小伙伴请联系我把自己的注册邮箱加入网站白名单,可以免回复看到本站所有Flag

PS:本站不是实验吧的官方站点,纯粹是个人博客,收取Flag费用仅是维持服务器费用,做站不易,且行窃珍惜!

微信二维码:
支付宝二维码: