這個(gè)以前寫過，見求數(shù)組的最長(zhǎng)子數(shù)組之和的最大值

這里說一下后面擴(kuò)展題目。
1. 簡(jiǎn)述

??? 1) 如果數(shù)組首尾相連，即允許找到一組數(shù)字(A[i],···,A[n-1], A[0],···, A[j])，請(qǐng)使其和最大，怎么辦？
??? 2) 如果題目要求返回最大子數(shù)組的位置，算法應(yīng)該如何改變？還能保持O(N)的復(fù)雜度么？

2. 思路

??? 第一個(gè)問題，書上給出了解答，即分為首尾相連和首尾不連兩種情況，對(duì)于首尾不連的情況，按照前面的思路就可以了，對(duì)于首尾相連的情況，那么必然包含A[N-1]與A[0]，然后從A[0]向后找最大的一段（按照不連的方法），從A[N-1]向前找最大的一段（按照不連的方法），然后得到A[0]-A[j] 與 A[i]-A[N-1]，如果j=<i，兩段不重合，兩端連起來就是解答；如果j>i，兩段重合，那么整個(gè)數(shù)組就是解答。這里我要說一下，關(guān)于兩段重合的情況，當(dāng)重合的時(shí)候，為什么說整個(gè)數(shù)組就是解答呢？這個(gè)點(diǎn)上我有質(zhì)疑，因?yàn)榧僭O(shè)數(shù)組為1,2,3,4,-1,4,3,2,1，那么左邊最大的一段是A[0]-A[N-1]，右邊最大的一段還是A[0]-A[N-1]那么按照書上的說法，此時(shí)重合，就是最大子數(shù)組為A[0]-A[N-1]，實(shí)際上應(yīng)該是去掉中間的-1的。

??? 針對(duì)上面的問題最穩(wěn)妥的方法應(yīng)該是每次循環(huán)移位數(shù)組一次，然后按照首尾不連的方法求最大和，這N長(zhǎng)度的數(shù)組，移位就是N種情況，每種情況O(N)的復(fù)雜度，一共是O(N^2)的復(fù)雜度。

??? 第二個(gè)問題，應(yīng)該很容易，每次更新開始位置和結(jié)束位置即可。

3. 參考

??? 編程之美，2.14節(jié)，求數(shù)組的子數(shù)組之和的最大值

總結(jié)

以上是生活随笔為你收集整理的编程之美-2.14-求数组的子数组之和的最大值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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