https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
今日從零開始刷到求數(shù)組中的最大連續(xù)子序和，我的思路是動態(tài)規(guī)劃顶岸，求帶最后一位的最大連續(xù)子序和，最終對比找到最大值辖佣。
官方題解提到了另一種分治法，引申出線段樹的概念
大致思想是 分段遞歸杯拐，求四個關(guān)鍵的參數(shù)進行對比求最大。
首先是數(shù)組的區(qū)間[l,r]端逼，其次取分治的中間點m凸郑，分成兩段[l,m] 和 [m+1,r]
對于一個區(qū)間 [l,r]裳食，我們可以維護四個量：
lSum 表示 [l,r] 內(nèi)以 l 為左端點的最大子段和
rSum 表示 [l,r] 內(nèi)以 r 為右端點的最大子段和
mSum 表示 [l,r] 內(nèi)的最大子段和
iSum 表示 [l,r] 的區(qū)間和
所以問題就變?yōu)檐搅ぃ乙骩l,r]的mSum，那么這個數(shù)據(jù)只有兩種情況而昨，要么是最長子序段不跨m也就是
max { [l,m]的mSum , [m+1,r]的mSum }；要么是跨m也就是 [l,m]的rSum + [m+1,r]的lSum着憨。所以最后的實現(xiàn)也就變?yōu)檫f歸务嫡，到最底的[l,l]長度為1甲抖，也就是四個關(guān)鍵參數(shù)都相等時心铃。往上return最后得出[l,r]的四個關(guān)鍵參數(shù)，最后比較大小即可去扣。
那么線段樹又是什么？這里官方最后給了段題外話，如下：
題外話
「方法二」相較于「方法一」來說哲戚，時間復(fù)雜度相同艾岂，但是因為使用了遞歸顺少，并且維護了四個信息的結(jié)構(gòu)體澳盐，運行的時間略長，空間復(fù)雜度也不如方法一優(yōu)秀叼耙，而且難以理解。那么這種方法存在的意義是什么呢筛婉？
對于這道題而言，確實是如此的入蛆。但是仔細(xì)觀察「方法二」，它不僅可以解決區(qū)間[0,n?1]哨毁，還可以用于解決任意的子區(qū)間[l,r] 的問題。如果我們把[0,n?1] 分治下去出現(xiàn)的所有子區(qū)間的信息都用堆式存儲的方式記憶化下來扼褪，即建成一顆真正的樹之后粱栖，我們就可以在 O(logn) 的時間內(nèi)求到任意區(qū)間內(nèi)的答案，我們甚至可以修改序列中的值闹究，做一些簡單的維護，之后仍然可以在 O(logn) 的時間內(nèi)求到任意區(qū)間內(nèi)的答案渣淤，對于大規(guī)模查詢的情況下，這種方法的優(yōu)勢便體現(xiàn)了出來价认。這棵樹就是上文提及的一種神奇的數(shù)據(jù)結(jié)構(gòu)——線段樹。
我的理解就是，這樣維護的樹結(jié)構(gòu)，所有的查詢都可以用接近一半的時間取獲得答案捶箱，會快于O(n)的動態(tài)規(guī)劃。但是這顆線段樹的節(jié)點新增和刪除都是需要重新計算關(guān)鍵參數(shù)的荠锭，維護起來比較麻煩，只能適用變更少证九，數(shù)值較為固定的場景、或可利用緩存結(jié)構(gòu)提前計算愧怜，可接受一定程度延時性的場景
