快捷導(dǎo)航

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

更新時(shí)間：2018年01月04日 08:52:19 作者：明柳夢(mèng)少

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

題目描述

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

思路：

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

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

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

步驟：

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

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

②如果前面的累加值為整數(shù)，那么繼續(xù)累加，即之前的累加值加上當(dāng)前第i個(gè)數(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: 輸入一個(gè)整形數(shù)組，有正數(shù)和負(fù)數(shù)，數(shù)組中的一個(gè)或連續(xù)多 
個(gè)整數(shù)組成一個(gè)子數(shù)組，O(n)時(shí)間求所有子數(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語(yǔ)言描述連續(xù)子數(shù)組的最大和的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專(zhuān)題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: