亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

最大總和子列表?

最大總和子列表?

qq_花開花謝_0 2019-10-10 16:49:55
對于這個問題,我感到困惑。寫函數mssl()(最小和子列表),將整數列表作為輸入。然后,它計算并返回輸入列表的最大和子列表的和。最大總和子列表是輸入列表的子列表(切片),其條目總和最大??兆恿斜矶x為總和為0。例如,列表的最大總和子列表[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]為[5, -2, 7, 7, 2] ,其條目的總和為19。如果我要使用此功能,它應該返回類似于>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]>>> mssl(l)19>>> mssl([3,4,5])12>>> mssl([-2,-3,-5])0我該怎么做?這是我目前的嘗試,但未產生預期的結果:def mssl(x):    ' list ==> int '    res = 0    for a in x:        if a >= 0:            res = sum(x)        return res    else:        return 0
查看完整描述

3 回答

?
MM們

TA貢獻1886條經驗 獲得超2個贊

這是最大的子陣列問題。Kadane的算法可以在O(n)時間和O(1)空間上求解它,其過程如下:


def mssl(x):

    max_ending_here = max_so_far = 0

    for a in x:

        max_ending_here = max(0, max_ending_here + a)

        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far


查看完整回答
反對 回復 2019-10-10
  • 3 回答
  • 0 關注
  • 864 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號