Java 面试题(4)—— 多线程
Java實現(xiàn)多線程有哪幾種方式。
implements Runnable, implements Callable,extends Thread
Callable和Future、FutureTask的了解。
Callable和 Future 是juc包下的接口。
Callable 可以異步執(zhí)行任務(wù),一般和 ExecutorService 的submit方法一起使用。
Future 可以監(jiān)聽任務(wù)是否結(jié)束,是否取消,取消任務(wù)和獲取結(jié)果(阻塞操作)。
FutureTask :
實現(xiàn)了Runnable和Future,所以兼顧兩者優(yōu)點。
既可以使用ExecutorService,也可以使用Thread。
?
Callable和Future的了解。
Callable和 Future 是juc包下的接口。
Callable 可以異步執(zhí)行任務(wù),一般和 ExecutorService 的submit方法一起使用。
Future 可以監(jiān)聽任務(wù)是否結(jié)束,是否取消,取消任務(wù)和獲取結(jié)果(阻塞操作)。
FutureTask :
實現(xiàn)了Runnable和Future,所以兼顧兩者優(yōu)點。
既可以使用ExecutorService,也可以使用Thread。
線程池的參數(shù)有哪些,在線程池創(chuàng)建一個線程的過程。
核心參數(shù):
workQueue : 執(zhí)行前用于保持任務(wù)的隊列。
keepAliveTime: 線程數(shù)量超過核心線程數(shù)量,等待工作的空閑線程超時(以納秒計)。
corePoolSize: 是保持活動狀態(tài)的最少的核心池大小
maximumPoolSize: 最大線程池
創(chuàng)建方式:
newCachedThreadPool:
創(chuàng)建一個可緩存線程池,如果線程池長度超過處理需要,可靈活回收空閑線程,若無可回收,則新建線程。
newFixedThreadPool:
創(chuàng)建一個定長線程池,可控制線程最大并發(fā)數(shù),超出的線程會在隊列中等待。
newScheduledThreadPool:?
創(chuàng)建一個定長線程池,支持定時及周期性任務(wù)執(zhí)行。
newSingleThreadExecutor:
創(chuàng)建一個單線程化的線程池,它只會用唯一的工作線程來執(zhí)行任務(wù),保證所有任務(wù)按照指定順序(FIFO, LIFO, 優(yōu)先級)執(zhí)行。
newWorkStealingPool:
jdk 1.8以后新出的,為了防止線程池啟用過多,導(dǎo)致cpu占用過多導(dǎo)致的項目宕機。適用于執(zhí)行多任務(wù),且每個任務(wù)耗時時間較短。 上面4種方式都有可能會出現(xiàn)占用cpu過高的情況。
創(chuàng)建過程:
1、判斷線程池里的核心線程是否都在執(zhí)行任務(wù),如果不是(核心線程空閑或者還有核心線程沒有被創(chuàng)建)則創(chuàng)建一個新的工作線程來執(zhí)行任務(wù)。如果核心線程都在執(zhí)行任務(wù),則進入下個流程。
2、線程池判斷工作隊列是否已滿,如果工作隊列沒有滿,則將新提交的任務(wù)存儲在這個工作隊列里。如果工作隊列滿了,則進入下個流程。
3、判斷線程池里的線程是否都處于工作狀態(tài),如果沒有,則創(chuàng)建一個新的工作線程來執(zhí)行任務(wù)。如果已經(jīng)滿了,則交給飽和策略來處理這個任務(wù)。
volitile關(guān)鍵字的作用,原理。
保證內(nèi)存可見性:
內(nèi)存可見性(Memory Visibility):所有線程都能看到共享內(nèi)存的最新狀態(tài)。
每次讀取前必須先從主內(nèi)存刷新最新的值。
每次寫入后必須立即同步回主內(nèi)存當(dāng)中。
防止指令重排序:
volatile關(guān)鍵字通過“內(nèi)存屏障”來防止指令被重排序。
為了實現(xiàn)volatile的內(nèi)存語義,編譯器在生成字節(jié)碼時,會在指令序列中插入內(nèi)存屏障來禁止特定類型的處理器重排序。
(案例是 單例模式的懶加載情況下,Happens-Before內(nèi)存模型的指令重排會產(chǎn)生兩個對象)
無法保證原子性:
這種原子性僅限于變量(包括引用)的讀和寫,無法涵蓋變量上的任何操作(如count++)
https://www.cnblogs.com/monkeysayhi/p/7654460.html
synchronized關(guān)鍵字的用法,優(yōu)缺點。
用法:
方法上、方法中、代碼塊,主要取決于鎖的對象。
優(yōu)點:
即線程之間保證同步關(guān)系。
Synchronized先天具有排他性、重入性。
jdk1.6以后對synchronized鎖進行了優(yōu)化,包含偏向鎖、輕量級鎖、重量級鎖。
缺點:
沒辦法設(shè)置獲取鎖的等待時間,可能會導(dǎo)致無限期地處于阻塞狀態(tài)。
對于讀多寫少的應(yīng)用而言是很不利的,因為即使多個讀者看似可以并發(fā)運行,但他們實際上還是串行的,并將最終導(dǎo)致并發(fā)性能的下降。
https://www.jianshu.com/p/d53bf830fa09
Lock接口有哪些實現(xiàn)類,使用場景是什么。
實現(xiàn)類 ReentrantLock,意思是“可重入鎖”,可以中斷獲取鎖操作,獲取鎖時候可以設(shè)置超時時間。
實現(xiàn)接口 ReadWriteLock 。讀寫鎖允許多個讀線程并發(fā)執(zhí)行,但是不允許寫線程與讀線程并發(fā)執(zhí)行,也不允許寫線程與寫線程并發(fā)執(zhí)行。
ReentrantReadWriteLock 實現(xiàn)于 ReadWriteLock,讀寫鎖允許同一時刻被多個讀線程訪問,但是在寫線程訪問時,所有的讀線程和其他的寫線程都會被阻塞。
公平性選擇:支持非公平性(默認(rèn))和公平的鎖獲取方式,吞吐量還是非公平優(yōu)于公平;
重入性:支持重入,讀鎖獲取后能再次獲取,寫鎖獲取之后能夠再次獲取寫鎖,同時也能夠獲取讀鎖;
鎖降級:遵循獲取寫鎖,獲取讀鎖再釋放寫鎖的次序,寫鎖能夠降級成為讀鎖。
https://www.jianshu.com/p/4a624281235e
synchronized和lock的對比。
lock可以讓嘗試獲得鎖的其他線程只等待一定時間。而synchronized修飾的代碼塊執(zhí)行完,才能釋放鎖。或線程執(zhí)行發(fā)生異常,JVM會讓線程自動釋放鎖。
讀操作和寫操作、寫操作和寫操作會發(fā)生沖突,但是讀操作和讀操作不發(fā)生沖突,Lock就可以允許這種可以同時進行的操作。(讀寫鎖)
Lock可以知道線程有沒有成功獲取到鎖。
當(dāng)競爭資源非常激烈時,Lock的性能會更好。(具體場景分析)
sychronized是不可中斷鎖,Lock可中斷。(可中斷鎖)
Lock可設(shè)置為公平鎖,按照請求鎖的順序分配鎖。(公平鎖)
可以和條件變量配合使用,對共享數(shù)據(jù)的多種狀態(tài)進行監(jiān)控。
https://blog.csdn.net/weixin_40255793/article/details/80786249
?
可重入鎖的用處及實現(xiàn)原理,寫時復(fù)制的過程,讀寫鎖,分段鎖(ConcurrentHashMap中的segment)。
定義:
若一個程序或子程序可以“在任意時刻被中斷然后操作系統(tǒng)調(diào)度執(zhí)行另外一段代碼,這段代碼又調(diào)用了該子程序不會出錯”,
則稱其為可重入(reentrant或re-entrant)的。即當(dāng)該子程序正在運行時,執(zhí)行線程可以再次進入并執(zhí)行它,
仍然獲得符合設(shè)計時預(yù)期的結(jié)果。與多線程并發(fā)執(zhí)行的線程安全不同,可重入強調(diào)對單個線程執(zhí)行時重新進入同一個子程序仍然是安全的。
原理:
每一個鎖關(guān)聯(lián)一個線程持有者和計數(shù)器,當(dāng)計數(shù)器為 0 時表示該鎖沒有被任何線程持有,那么任何線程都可能獲得該鎖而調(diào)用相應(yīng)的方法;
當(dāng)某一線程請求成功后,JVM會記下鎖的持有線程,并且將計數(shù)器置為 1;此時其它線程請求該鎖,則必須等待;
而該持有鎖的線程如果再次請求這個鎖,就可以再次拿到這個鎖,同時計數(shù)器會遞增;
當(dāng)線程退出同步代碼塊時,計數(shù)器會遞減,如果計數(shù)器為 0,則釋放該鎖。
場景:
可重入鎖主要用在線程需要多次進入臨界區(qū)代碼時,需要使用可重入鎖。
具體的例子,比如上文中提到的一個synchronized方法需要調(diào)用另一個synchronized方法時。
讀寫鎖:
讀寫鎖依賴自定義同步器實現(xiàn)同步功能,讀寫狀態(tài)也就是同步器的同步狀態(tài)。讀寫鎖將整形變量切分成兩部分,高16位表示讀,低16位表示寫。
讀寫鎖通過位運算計算各自的同步狀態(tài)。
假設(shè)當(dāng)前同步狀態(tài)的值為c,寫狀態(tài)就為c&0x0000FFFF,讀狀態(tài)為c >>> 16(無符號位補0右移16位)。
當(dāng)寫狀態(tài)增加1狀態(tài)變?yōu)閏+1,當(dāng)讀狀態(tài)增加1時,狀態(tài)編碼就是c+(1 <<< 16)。
獲取讀鎖:
ThreadLocal線程本地對象,將每個線程獲取鎖的次數(shù)保存到每個線程內(nèi)部,這樣釋放鎖的時候就不會影響到其它的線程。?
tryAcquireShared 失敗后使用 fullTryAcquireShared cas獲取鎖。
首先讀寫鎖中讀狀態(tài)為所有線程獲取讀鎖的次數(shù),由于是可重入鎖,又因為每個鎖獲取的讀鎖的次數(shù)由每個鎖的本地變量ThreadLocal對象去保存因此增加了讀取獲取的流程難度,
在每次獲取讀鎖之前都會進行一次判斷是否存在獨占式寫鎖,如果存在獨占式寫鎖就直接返回獲取失敗,進入同步隊列中。
如果當(dāng)前沒有寫鎖被獲取,則線程可以獲取讀鎖,由于共享鎖的存在,每次獲取都會判斷線程的類型,以便每個線程獲取同步狀態(tài)的時候都在其對應(yīng)的本地變量上進行自增操作。
獲取寫鎖:
獲取寫鎖相比獲取讀鎖就簡單了很多,在獲取讀鎖之前只需要判斷當(dāng)前是否存在讀鎖,如果存在讀鎖那么獲取失敗,
進而再判斷獲取寫鎖的線程是否為當(dāng)前線程如果不是也就是失敗否則就是重入鎖在已有的狀態(tài)值上進行自增。
讀寫鎖降級:
鎖降級就是從寫鎖降級成為讀鎖。在當(dāng)前線程擁有寫鎖的情況下,再次獲取到讀鎖,隨后釋放寫鎖的過程就是鎖降級。
分段鎖:
jdk 8以前,ConcurrentHashMap分段鎖代替HashTable的獨占鎖。Segment繼承了重入鎖ReentrantLock,有了鎖的功能,同時含有類似HashMap中的數(shù)組加鏈表結(jié)構(gòu)。
jdk 8以后已經(jīng)棄用分段鎖了,原因由以下幾點:
加入多個分段鎖浪費內(nèi)存空間。
生產(chǎn)環(huán)境中, map 在放入時競爭同一個鎖的概率非常小,分段鎖反而會造成更新等操作的長時間等待。
為了提高 GC 的效率。
https://www.cnblogs.com/wait-pigblog/p/9350569.html
悲觀鎖,樂觀鎖,優(yōu)缺點,CAS有什么缺陷,該如何解決。
樂觀鎖:
即認(rèn)為讀多寫少,并發(fā)的修改少,別人每次拿到數(shù)據(jù)都不會修改,所以不會上鎖。
更新的時候會校驗一下這個數(shù)據(jù)有沒有被更新過。具體策略是更新前先獲取當(dāng)前版本號,
然后和上次的版本號比較,一樣再更新,如果失敗則要重復(fù)讀-比較-寫的操作。
使用:AQS框架下的鎖則是先嘗試cas樂觀鎖去獲取鎖,獲取不到,才會轉(zhuǎn)換為悲觀鎖,如RetreenLock。
悲觀鎖:
悲觀鎖即認(rèn)為寫多,并發(fā)的修改多,每次拿到數(shù)據(jù)都會上鎖,別人想讀寫這個數(shù)據(jù)就會block直到拿到鎖。
使用:synchronized
CAS 優(yōu)點:
非阻塞的輕量級的樂觀鎖,通過CPU指令實現(xiàn),在資源競爭不激烈的情況下性能高,
相比synchronized重量鎖,synchronized會進行比較復(fù)雜的加鎖、解鎖和喚醒操作。
CAS 缺點:?
1. ABA問題。即更新之前版本是A,中間更新由A->B->A,此時拿到的線程以為沒更新過。
java的原子類AtomicStampedReference,通過控制變量值的版本號來保證CAS的正確性。
具體解決思路就是在變量前追加上版本號,每次變量更新的時候把版本號或者時間戳加一,
那么A - B - A就會變成1A - 2B - 3A
2. 自旋時間過長,消耗CPU資源,如果資源競爭激烈,多線程自旋長時間消耗資源。
https://blog.csdn.net/qq_20499001/article/details/90315061
非公平鎖,公平鎖的區(qū)別。
多線程執(zhí)行的順序緯度將鎖分為公平鎖和非公平鎖。
公平鎖:加鎖前先查看是否有排隊等待的線程,有的話優(yōu)先處理排在前面的線程,先來先得。
非公平鎖:加鎖時直接進行一次CAS嘗試獲取鎖,如果沒有獲取到,
再判斷一次(tryAcquire 方法中如果鎖空閑,則直接獲取)沒有獲取到,去隊尾排隊。
ReentrantLock 支持兩種鎖。
ReentrantLock 的 公平 tryAcquire 方法注釋:
Fair version of tryAcquire. ?Don't grant access unless recursive call or no waiters or is first.
tryAcquire 的公平版本。除非是遞歸調(diào)用或沒有等待者,否則不允許訪問。
非公平 tryAcquire 方法注釋:
Performs non-fair tryLock. ?tryAcquire is implemented in subclasses, but both need nonfair try for trylock method.
執(zhí)行非公平的tryLock。 tryAcquire是在子類中實現(xiàn)的,但兩者都需要 trylock 方法的非公平嘗試。
兩者的區(qū)別在于 tryAcquire 中判斷state = 0(鎖的引用為0),非公平直接調(diào)用CAS,而公平鎖要保證當(dāng)前線程之前沒有線程了,才可以CAS.
使用:
更多的是直接使用非公平鎖;非公平鎖比公平鎖性能高5-10倍,因為公平鎖需要在多核情況下維護一個隊列,
如果當(dāng)前線程不是隊列的第一個無法獲取鎖,增加了線程切換次數(shù)。
https://www.jianshu.com/p/2ada27eee90b
http://www.cnblogs.com/darrenqiao/p/9211178.html
偏向鎖、輕量級鎖、自旋鎖、重量級鎖的區(qū)別。
自旋鎖:
如果持有鎖的資源在很短時間內(nèi)可以釋放鎖,其他線程就不需要進入阻塞狀態(tài),只需要等一下(自旋),
等有鎖的線程釋放后立即獲取鎖。這樣避免用戶線程和內(nèi)核之間切換的消耗。
自旋是需要消耗cpu的,需要設(shè)置自旋的時間, 超過時間線程進入阻塞。
優(yōu)點:
減少線程阻塞,對于鎖競爭不激烈、持有鎖時間很短的情況下,性能有很大提升,自旋
的cpu消耗會小于線程阻塞再喚醒(線程發(fā)生兩次上下文切換)
缺點:
如果線程競爭資源多,而且線程持有鎖的時間很長的話,自旋等待消耗的cpu要
大于線程阻塞再喚醒的消耗,造成cpu的浪費。
自旋鎖時間閾值的設(shè)定:
JDK 1.6以后引入了適應(yīng)性自旋鎖,自旋的時間不在是固定的了,
而是由前一次在同一個鎖上的自旋時間以及鎖的擁有者的狀態(tài)來決定。
基本認(rèn)為一個線程上下文切換的時間是最佳的一個時間。
JVM的優(yōu)化:
如果平均負(fù)載<cpu的數(shù)量,則一直自旋
如果超過cpu數(shù)量/2個線程正在自旋,則后來線程直接阻塞
如果正在自旋的線程發(fā)現(xiàn)Owner發(fā)生了變化則延遲自旋時間(自旋計數(shù))或進入阻塞
如果CPU處于節(jié)電模式則停止自旋
自旋時間的最壞情況是CPU的存儲延遲(CPU A存儲了一個數(shù)據(jù),到CPU B得知這個數(shù)據(jù)直接的時間差)
自旋時會適當(dāng)放棄線程優(yōu)先級之間的差異
JDK7以后自旋參數(shù)由JVM控制
偏向鎖:
鎖標(biāo)識位01
偏向鎖,顧名思義,它會偏向于第一個訪問鎖的線程,
如果在運行過程中,同步鎖只有一個線程訪問,就會給線程加一個偏向鎖,再次訪問不需要CAS。如果在運行過程中,遇到了其他線程搶占鎖,則持有偏向鎖的線程會被掛起,JVM會消除它身上的偏向鎖,將鎖恢復(fù)到標(biāo)準(zhǔn)的輕量級鎖。
過程:
Mark Word的偏向鎖標(biāo)識為01,則有偏向鎖。
如果是可偏向狀態(tài),比較訪問線程的ID是否指向當(dāng)前線程。
如果是的話,直接同步,如果不是,會檢查上一個ID指向的線程是否存活。
如果掛了,則新的線程持有偏向鎖,否則的話,升級為輕量級鎖(CAS替換Mark Word失敗)。
偏向鎖會先撤銷再升級,撤銷會導(dǎo)致STW。
輕量級鎖:
鎖標(biāo)識位00
輕量級鎖是由偏向鎖升級來的。
是指兩個線程交替獲取鎖或者另一個線程自旋閾值時間內(nèi)獲得鎖,這種是輕量級鎖。
此時Mark Word指向的是當(dāng)前線程的棧幀。
如果超過閾值時間導(dǎo)致另一個線程進入阻塞,則輕量級鎖釋放升級為重量級鎖。
重量級鎖:
鎖標(biāo)識位10
重量級鎖是由輕量級鎖升級來的。
多個線程競爭同一個鎖。
此時Mark Word指向的是持有重量級鎖線程的棧幀。
重量級鎖Synchronized:
JVM每次從隊列的尾部取出一個數(shù)據(jù)用于鎖競爭候選者(OnDeck),但是并發(fā)情況下,ContentionList會被大量的并發(fā)線程進行CAS訪問,為了降低對尾部元素的競爭,JVM會將一部分線程移動到EntryList中作為候選競爭線程。Owner線程會在unlock時,將ContentionList中的部分線程遷移到EntryList中,并指定EntryList中的某個線程為OnDeck線程(一般是最先進去的那個線程)。Owner線程并不直接把鎖傳遞給OnDeck線程,而是把鎖競爭的權(quán)利交給OnDeck,OnDeck需要重新競爭鎖。這樣雖然犧牲了一些公平性,但是能極大的提升系統(tǒng)的吞吐量,在JVM中,也把這種選擇行為稱之為“競爭切換”。
OnDeck線程獲取到鎖資源后會變?yōu)镺wner線程,而沒有得到鎖資源的仍然停留在EntryList中。如果Owner線程被wait方法阻塞,則轉(zhuǎn)移到WaitSet隊列中,直到某個時刻通過notify或者notifyAll喚醒,會重新進去EntryList中。
Synchronized是非公平鎖。 Synchronized在線程進入ContentionList時,等待的線程會先嘗試自旋獲取鎖,如果獲取不到就進入ContentionList,這明顯對于已經(jīng)進入隊列的線程是不公平的,還有一個不公平的事情就是自旋獲取鎖的線程還可能直接搶占OnDeck線程的鎖資源。
ContentionList ——> EntryList ——> OnDeck ——> Owner ——> WaitSet ——> EntryList(wait后notify回到EntryList)
https://blog.csdn.net/zqz_zqz/article/details/70233767
https://blog.csdn.net/tian251yu/article/details/80638104
?
ABC三個線程如何保證順序執(zhí)行。
公平鎖的方式:
ReentrantLock lock = new ReentrantLock(true);
lock.lock();
BlockingQueue的方式:
LinkedBlockingQueue queue = new LinkedBlockingQueue();
queue.put();
queue.poll();
線程的狀態(tài)都有哪些。
新建(New):新建了一個線程對象。
就緒(Runnable):線程創(chuàng)建后,調(diào)用了start方法。該線程存在于"可運行線程池"中,只等待cpu的使用權(quán)。
運行(Running):就緒的線程獲得cpu,運行。
阻塞(Blocked):運行的線程因為某些原因(調(diào)用wait方法)放棄cpu使用權(quán),暫停運行,
直到線程喚醒后進入就緒狀態(tài)(調(diào)用notify方法),才有機會運行。
https://www.cnblogs.com/jijijiefang/articles/7222955.html
sleep和wait的區(qū)別。
sleep是Thread類的方法,wait是Object類的方法。
sleep沒有釋放鎖,wait方法釋放了鎖,被wait的線程重新進入阻塞線程池,
直到被其他線程調(diào)用notify/notifyAll后進入就緒狀態(tài)。
sleep(milliseconds)可以用時間指定使它自動喚醒過來,如果時間不到只能調(diào)用interrupt()強行打斷。
Thread.Sleep(0)的作用是“觸發(fā)操作系統(tǒng)立刻重新進行一次CPU競爭”。
https://www.cnblogs.com/plmnko/archive/2010/10/15/1851854.html
notify和notifyall的區(qū)別。
notify和notifyAll之間的關(guān)鍵區(qū)別在于notify()只會喚醒一個線程,而notifyAll方法將喚醒所有線程。
其實,每個對象都擁有兩個池,分別為鎖池(EntrySet)和(WaitSet)等待池。
鎖池:假如已經(jīng)有線程A獲取到了鎖,這時候又有線程B需要獲取這把鎖(比如需要調(diào)用synchronized修飾的方法或者需要執(zhí)行synchronized修飾的代碼塊),由于該鎖已經(jīng)被占用,所以線程B只能等待這把鎖,這時候線程B將會進入這把鎖的鎖池。
等待池:假設(shè)線程A獲取到鎖之后,由于一些條件的不滿足(例如生產(chǎn)者消費者模式中生產(chǎn)者獲取到鎖,然后判斷隊列為滿),此時需要調(diào)用對象鎖的wait方法,那么線程A將放棄這把鎖,并進入這把鎖的等待池。
如果有其他線程調(diào)用了鎖的notify方法,則會根據(jù)一定的算法從等待池中選取一個線程,將此線程放入鎖池。
如果有其他線程調(diào)用了鎖的notifyAll方法,則會將等待池中所有線程全部放入鎖池,并爭搶鎖。
鎖池與等待池的區(qū)別:等待池中的線程不能獲取鎖,而是需要被喚醒進入鎖池,才有獲取到鎖的機會。
https://blog.csdn.net/liuzhixiong_521/article/details/86677057
ThreadLocal的了解,實現(xiàn)原理。
ThreadLocal提供一個線程(Thread)局部變量,訪問到某個變量的每一個線程都擁有自己的局部變量。
每個Thread的對象都有一個ThreadLocalMap,當(dāng)創(chuàng)建一個ThreadLocal的時候,就會將該ThreadLocal對象添加到該Map中,其中鍵就是ThreadLocal,值可以是任意類型。
https://www.jianshu.com/p/ee8c9dccc953
?
AQS的原理。
J.U.C是基于AQS實現(xiàn)的,AQS是一個同步器,設(shè)計模式是模板模式。
核心數(shù)據(jù)結(jié)構(gòu):雙向鏈表(CLH) + state(鎖狀態(tài))
底層操作:CAS
兩種資源共享方式:Exclusive(獨占,只有一個線程能執(zhí)行,如ReentrantLock)和Share(共享,多個線程可同時執(zhí)行,如Semaphore/CountDownLatch)。
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯,堅持創(chuàng)作打卡瓜分現(xiàn)金大獎總結(jié)
以上是生活随笔為你收集整理的Java 面试题(4)—— 多线程的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: webstorm破解版
- 下一篇: 53.Maximum Subarray