Python語言描述連續(xù)子數(shù)組的最大和
題目描述
HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學(xué)。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應(yīng)該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠??？(子向量的長度至少是1)
思路：
最大和連續(xù)子數(shù)組一定有如下幾個特點：
1、第一個不為負數(shù)
2、如果前面數(shù)的累加值加上當(dāng)前數(shù)后的值會比當(dāng)前數(shù)小，說明累計值對整體和是有害的；如果前面數(shù)的累加值加上當(dāng)前數(shù)后的值比當(dāng)前數(shù)大或者等于，則說明累計值對整體和是有益的。
步驟：
1、定義兩個變量，一個用來存儲之前的累加值，一個用來存儲當(dāng)前的最大和。遍歷數(shù)組中的每個元素，假設(shè)遍歷到第i個數(shù)時：
①如果前面的累加值為負數(shù)或者等于0，那對累加值清0重新累加，把當(dāng)前的第i個數(shù)的值賦給累加值。
②如果前面的累加值為整數(shù)，那么繼續(xù)累加，即之前的累加值加上當(dāng)前第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)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
相關(guān)文章
這篇文章主要介紹了pandas 選取行和列數(shù)據(jù)的方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-08-08
pymysql.err.DataError:1366的報錯解決
通過python把數(shù)據(jù)同步至mysql數(shù)據(jù)庫的過程中,遇到錯誤,本文主要介紹了pymysql.err.DataError:1366的報錯解決,具有一定的參考價值,感興趣的可以了解一下2024-05-05
這篇文章主要介紹了基于Python獲取城市近7天天氣預(yù)報,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-11-11
詳解Python常用標準庫之時間模塊time和datetime
time和datetime是Python中常用的兩個時間模塊，本文將通過示例詳細為大家講講二者的使用方法，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)學(xué)習(xí)2022-05-05
python數(shù)字圖像處理之基本形態(tài)學(xué)濾波
這篇文章主要為大家介紹了python數(shù)字圖像處理之基本形態(tài)學(xué)濾波示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
Pytorch卷積神經(jīng)網(wǎng)絡(luò)resent網(wǎng)絡(luò)實踐
這篇文章主要為大家介紹了Pytorch卷積神經(jīng)網(wǎng)絡(luò)resent網(wǎng)絡(luò)實踐，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
今天小編就為大家分享一篇對python csv模塊配置分隔符和引用符詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
這篇文章主要給大家介紹了關(guān)于如何利用python實現(xiàn)冒泡排序算法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用python具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
這篇文章主要介紹了python 瀑布線指標編寫實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
python自動發(fā)送測試報告郵件功能的實現(xiàn)
這篇文章主要介紹了python自動發(fā)測試報告郵件功能的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01