Python語言描述連續(xù)子數(shù)組的最大和

更新時間：2018年01月04日 08:52:19 作者：明柳夢少

這篇文章主要介紹了Python語言描述連續(xù)子數(shù)組的最大和，具有一定借鑒價值,需要的朋友可以參考下

題目描述

HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠住？(子向量的長度至少是1)

思路：

最大和連續(xù)子數(shù)組一定有如下幾個特點：

1、第一個不為負數(shù)

2、如果前面數(shù)的累加值加上當前數(shù)后的值會比當前數(shù)小，說明累計值對整體和是有害的；如果前面數(shù)的累加值加上當前數(shù)后的值比當前數(shù)大或者等于，則說明累計值對整體和是有益的。

步驟：

1、定義兩個變量，一個用來存儲之前的累加值，一個用來存儲當前的最大和。遍歷數(shù)組中的每個元素，假設(shè)遍歷到第i個數(shù)時：

①如果前面的累加值為負數(shù)或者等于0，那對累加值清0重新累加，把當前的第i個數(shù)的值賦給累加值。

②如果前面的累加值為整數(shù)，那么繼續(xù)累加，即之前的累加值加上當前第i個數(shù)的值作為新的累加值。

2、判斷累加值是否大于最大值：如果大于最大值，則最大和更新；否則，繼續(xù)保留之前的最大和

# -*- coding: utf-8 -*- 
""" 
Date: Thu Nov 02 11:00:40 2017 
 
Created by @author: xiaoguibao 
 
E-mail: mingliumengshao@163.com 
 
連續(xù)子數(shù)組的最大和 
Content: 輸入一個整形數(shù)組，有正數(shù)和負數(shù)，數(shù)組中的一個或連續(xù)多 
個整數(shù)組成一個子數(shù)組，O(n)時間求所有子數(shù)組的和的最大值。 
 
""" 
 
def function(lists): 
  max_sum = lists[0] 
  pre_sum = 0 
  for i in lists: 
    if pre_sum < 0: 
      pre_sum = i 
    else: 
      pre_sum += i 
    if pre_sum > max_sum: 
      max_sum = pre_sum 
  return max_sum 
 
def main(): 
  lists=[6,-3,1,-2,7,-15,1,2,2] 
  print function(lists) 
   
if __name__ == "__main__": 
  main()

總結(jié)

以上就是本文關(guān)于Python語言描述連續(xù)子數(shù)組的最大和的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

您可能感興趣的文章: