最大子數列問題:Kadane算法,線上處理算法,問題描述,暴力方法,一個簡單的最佳

在計算機科學中，最大子數列問題的目標是在數列的一維方向找到一個連續的子數列，使該子數列的和最大。例如，對一個數列 −2, 1, −3, 4, −1, 2, 1, −5, 4，其連續子數列中和最大的是 4, −1, 2, 1, 其和為6。

該問題最初由布朗大學的Ulf Grenander教授於1977年提出，當初他為了展示數字圖像中一個簡單的最大似然估計模型。不久之後卡內基梅隆大學的Jay Kadane提出了該問題的線性算法。

基本介紹

中文名：最大子數列問題
領域：計算機

Kadane算法,線上處理算法,問題描述,暴力方法,一個簡單的最佳化,分而治之,線上處理,

Kadane算法

Kadane算法掃描一次整個數列的所有數值，在每一個掃描點計算以該點數值為結束點的子數列的最大和（正數和）。該子數列由兩部分組成：以前一個位置為結束點的最大子數列、該位置的數值。因為該算法用到了“最佳子結構”（以每個位置為終點的最大子數列都是基於其前一位置的最大子數列計算得出），該算法可看成動態規劃的一個例子。

給定一個數列，例如【−2, 1, −3, 4, −1, 2, 1, −5, 4】，求一個連續的數列使得數列內的元素和最大，示例中最大子數列應該是【4, −1, 2, 1】, 求和值為6。
這個問題是可以衍生到一些變種問題，如尋找數列中最大乘積序列，且要求序列中，相鄰元素間隔不超過限定值等，常出現在筆試面試編程題中。
該問題最早於1977年提出，但是直到1984年才被Jay Kadane 發現了線性時間的最優解法，所以算法雖然長度很短，但其實並不容易理解。
算法描述：
遍歷該數組，在遍歷過程中，將遍歷到的元素依次累加起來，當累加結果小於或等於0時，從下一個元素開始，重新開始累加。
累加過程中，要用一個變數(max_so_far)記錄所獲得過的最大值
一次遍歷之後，變數 max_so_far 中存儲的即為最大子片段的和值。

此處為python 代碼，變數A 傳入數組。

defmax_subarray(A):max_ending_here=max_so_far=0forxinA:max_ending_here=max(0,max_ending_here+x)max_so_far=max(max_so_far,max_ending_here)returnmax_so_far

首先，題目中有一個隱含的設定， 最大子片段是可以為空的，空片段的和值是0。這一點必須要明確，不然會無法理解算法的正確性，所以當給定的數列中，求和為負數的時候，例如【-2，1， -3】，算法會返回最大求和值0，因為默認該數組的最大子片段是一個空序列。

理解此算法的關鍵在於:

最大子片段中不可能包含求和值為負的前綴。例如【-2， 1，4】必然不能是最大子數列，因為去掉值為負的前綴後【-2，1】，可以得到一個更大的子數列【4】、
所以在遍歷過程中，每當累加結果成為一個非正值時，就應當將下一個元素作為潛在最大子數列的起始元素，重新開始累加。
由於在累加過程中，出現過的最大值都會被記錄，且每一個可能成為 最大子數列起始元素 的位置，都會導致新一輪的累加，這樣就保證了答案搜尋過程的完備性和正確性。

算法可用如下Python代碼實現：

def max_subarray(A):    max_ending_here = max_so_far = A[0]    for x in A[1:]:        max_ending_here = max(x, max_ending_here + x)        max_so_far = max(max_so_far, max_ending_here)    return max_so_far

該問題的一個變種是：如果數列中含有負數元素，允許返回長度為零的子數列。該問題可用如下代碼解決：

def max_subarray(A):    max_ending_here = max_so_far = 0    for x in A:        max_ending_here = max(0, max_ending_here + x)        max_so_far = max(max_so_far, max_ending_here)    return max_so_far

這種算法稍作修改就可以記錄最大子數列的起始位置。Kadane算法時間複雜度為O(n)，空間複雜度為O(1)。

線上處理算法

問題描述

最大連續子數列和一道很經典的算法問題，給定一個數列，其中可能有正數也可能有負數，我們的任務是找出其中連續的一個子數列（不允許空序列），使它們的和儘可能大。我們一起用多種方式，逐步最佳化解決這個問題。

暴力方法

求出所有可能連續子列的和，時間複雜度O(N^3)

int MaxSubSequm1(int A[], int N){    int ThisSum, MaxSum = 0;    int i, j, k;    for (i = 0; i < N; i++)  {         for (j = i; j < N; j++){            ThisSum = 0;             for (k = i; k <= j; k++)                     ThisSum += A[k];            if (ThisSum>MaxSum)               MaxSum = ThisSum;        }    }  return MaxSum; }

一個簡單的最佳化

很顯然上面的算法中，在計運算元列和時，可以利用前一步計算和的結果，不需要每次從頭累加。時間複雜度O(N^2)。

int MaxSubSequm1(int A[], int N){    int ThisSum, MaxSum = 0;    int i, j, k;    for (i = 0; i < N; i++)  {       for (j = i; j < N; j++){                 ThisSum +=A[j];                             if (ThisSum>MaxSum)                   MaxSum = ThisSum;                }                   }  return MaxSum;}

分而治之

將問題一分為二，縮小問題規模，遞歸求解。
此處求解過程中要從中間基準點開始，掃描求出跨界的最大連續子列和，然後和左右邊的解比較求出最終的結果。
時間複雜度O(N*logN)

線上處理

我們可以通過拋棄負子列，保證最大子列和遞增。當掃描一遍，最大子列和不再遞增時，當前的最大子列和即為我們的解。這是最優算法，時間複雜度O(N)。

int MaxSubseqSum4(int A[], int N){    int ThisSum, MaxSum;    int i;    ThisSum = MaxSum = 0;     for (i = 0; i < N; i++){         ThisSum += A[i];      if (ThisSum>MaxSum)            MaxSum = ThisSum;         else if (ThisSum < 0)           ThisSum = 0;   }    return MaxSum;}

最大子數列問題