求解最大子序列和

求解最大子序列和

更新於 發佈於 閱讀時間約 3 分鐘

問題如下,在這串連續數列中 : -7、8、2、9、3、-4、-8、7、9、-5,請找出最大的子序列之和、以及最小的子序列之和,求最大子序列和 ~ MaxSubSum,是用途很廣的敘述統計工具,例如應用於求解 MDD、描述價格資料期間內最大的累積上漲點數...等

Kadane's 提供的算法邏輯如下 :
1. 該元素如果是負值,就不是子序列起點;
2. 同理,子序和為負值亦不列入集合內
僅需兩個判斷條件,即可建構程式碼求解

Excel VBA程式碼提供如下

Public Function MaxSubArraySum(ByVal InputData As Range, ByVal Output As Variant) As Variant
'Output=1 求解最大子序列和
'Output=-1 求解最小子序列和
Dim ArrDataX() As Variant
Dim DataCount As Variant
Dim ii As Variant
Dim thisSum As Variant
Dim MaxSum As Variant

ArrDataX = InputData '抓取Excel 欄位的數據,存入VBA控制的陣列
DataCount = InputData.Count '記錄抓取的資料筆數

thisSum = 0
MaxSum = 0

For ii = 1 To DataCount
thisSum = thisSum + (Output) * ArrDataX(ii, 1)
If thisSum > MaxSum Then MaxSum = thisSum
If thisSum < 0 Then thisSum = 0
Next 'For ii = 1 To DataCount
MaxSubArraySum = (Output) * MaxSum '求解最大子序列和
End Function

avatar-img
Piemann的沙龍
21會員
113內容數
留言
avatar-img
留言分享你的想法!
Piemann的沙龍 的其他內容
2025.04.01 明顯的,Cheat GPT 功能越來越強大,應用範圍只多不少 !! 輸入問題如下 : 1. 有一個隨機碼,長度為5個不重複的數字及小寫英文字母所組成, 例如 e2k9z、ju72d、...,共有一萬筆數據 2. 請設計一個雜湊函數方案,讓隨機碼對應到實數整數空間 3.
龐氏騙局定義 : 由後繼者的投資本金,支付前期投資者的紅利,謂之 !! 案例 : 制定獎勵生育誘因、追求人口紅利之國策,其實就是隱形的龐氏騙局 !! 那生命的意義,除了在於繼起宇宙生命之外,還有啥意義 ? 對曰 : 還得創造傳奇 ! 那如何創造傳奇 ? 對曰 : 確定目標、集中資源、專研
1990~1991之際,爆發第一次波灣戰爭(市場稱為第三次石油危機),起因是兩伊戰爭期間,伊拉克對科威特欠下巨債,戰後伊拉克藉端生事,要求取消相關債權,科威特不願意,因此伊拉克便開始調動軍隊部署於邊境(1990.七月中下旬),緊張局勢快速升溫,及至入侵(1990.08.02)科威特佔領全境後(199
2025.04.01 明顯的,Cheat GPT 功能越來越強大,應用範圍只多不少 !! 輸入問題如下 : 1. 有一個隨機碼,長度為5個不重複的數字及小寫英文字母所組成, 例如 e2k9z、ju72d、...,共有一萬筆數據 2. 請設計一個雜湊函數方案,讓隨機碼對應到實數整數空間 3.
龐氏騙局定義 : 由後繼者的投資本金,支付前期投資者的紅利,謂之 !! 案例 : 制定獎勵生育誘因、追求人口紅利之國策,其實就是隱形的龐氏騙局 !! 那生命的意義,除了在於繼起宇宙生命之外,還有啥意義 ? 對曰 : 還得創造傳奇 ! 那如何創造傳奇 ? 對曰 : 確定目標、集中資源、專研
1990~1991之際,爆發第一次波灣戰爭(市場稱為第三次石油危機),起因是兩伊戰爭期間,伊拉克對科威特欠下巨債,戰後伊拉克藉端生事,要求取消相關債權,科威特不願意,因此伊拉克便開始調動軍隊部署於邊境(1990.七月中下旬),緊張局勢快速升溫,及至入侵(1990.08.02)科威特佔領全境後(199