從股票買賣問題轉(zhuǎn)換成為一個(gè)求最大子數(shù)組問題

?

天	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
價(jià)格	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
變化		13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

? ? 暴力求解所花費(fèi)的時(shí)間是O(n^2) 采用分治技術(shù)來求解最大子數(shù)組問題，假定要求的數(shù)組為A[low..high]的最大子數(shù)組。 將子數(shù)組劃分為兩個(gè)規(guī)模盡可能相等的子數(shù)組，也就是說找到子數(shù)組的中央位置，比如mid，然后考慮求解兩個(gè)子數(shù)組： A[low..mid]和A[mid..high]的最大子數(shù)組，然后還一個(gè)是跨越中點(diǎn)的子數(shù)組。 下面是一個(gè)示意圖 ? ?

轉(zhuǎn)載于:https://www.cnblogs.com/tuhooo/p/5592894.html

總結(jié)

以上是生活随笔為你收集整理的分治策略之最大子数组问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。