1.問題的定義
顧名思義，最大子數組問題是求一個數組Array中“和最大的非空連續子數組“，這樣的連續子數組我們叫做最大子數組，它的應用也有
很多，比如說找出時間序列中兩個時間節點使得這兩個時間節點對應的值的落差最大，如下圖：
對于這類問題，通過求原始時間序列的一階差分得到序列Array，此時求得Array的最大子數組便是原問題的解。
2.問題的求解
2.1暴力求解
這是最容易想到的辦法，對于規模為n的問題，需要嘗試C(2,n)次(代表組合數，這裡不友善打公式)，因為每次的處理時間也至少是常量，是以，這種方法的運作的時間下界是n的平方，當n很大的時候，這種方法不可取。下面先介紹一種時間複雜度上界為n平方的分治的遞歸算法，最後再分析一種非遞歸的線性算法。
2.2分治算法
這裡我們是求“一個最大子數組”，而不是求“最大子數組”，因為最大子數組可能有多個，另外，很顯然隻有數組中有負數的時候問題才有意義。
分治算法的關鍵是問題如何劃分為兩個（或多個）子問題，之後又是如何進行合并，劃分問題成為兩個規模更小的子問題的分析如下：
找到數組Array的中央位置mid，然後考慮求解Array[low,...,mid]和Array[mid+1,...,high]，而Array[low,...,high]的任何連續子數組Array[i,...,j]所處的位置必然是以下三種情況之一：
(1)完全位于子數組Array[low,...,mid]中，是以low=<i=<j=<mid;
(2)完全位于子數組Array[mid+1,...,high]中，是以mid<i=<j=<high;
(3)跨越中點，是以low=<i=<mid<j=<high;
是以數組Array[low,...,high]的一個最大子數組所處的位置必然是這三種的一種，于是我們可以遞歸求解Array[low,...,mid]各Array[mid+1,...,high]的最大子數組，因為這兩個子問題仍然是最大子數組的問題，隻是規模變小了，接着我們再求跨越中點的最大子數組，結果取三者中最大的。
現在我們先求跨越中點的最大子數組問題，這個問題并不是規模更小的問題，因為它要求子數組必須跨越中點，我們隻需要求出形如
Array[i,...,mid]的最大子數組和形如Array[mid+1,...,j]的最大子數組，合并即可，對于這個子程式，我們傳回兩端的索引和最大子數組
的和（後一個子程式也傳回這種形式的結果）,我們定義傳回結果為結構體類型：
<span style="font-size:14px;">//定義類型為結構體類型的傳回結果
struct value
{
int index_left;
int index_right;
int sum;
};</span>
接下來是求跨越中點的最大子數組子程式：
//最大子數組跨越中點的情況
struct value find_max_crossing_subarray(int arr[],int low,int mid,int high)
{
struct value result;
int left_sum = MIN,right_sum = MIN;
int sum;
int max_left,max_right;
//找到左邊數組的最大子數組
sum = 0;
int i;
for(i = mid;i > low-1;i--)
{
sum += arr[i];
if(sum > left_sum)
{
left_sum = sum;
max_left = i;
}
}
//找到右邊數組的最大子數組
sum = 0;
for(i = mid+1;i < high+1;i++)
{
sum += arr[i];
if(sum > right_sum)
{
right_sum = sum;
max_right = i;
}
}
result.index_left = max_left;
result.index_right = max_right;
result.sum = left_sum + right_sum;
return result;
}
很顯然，這個子程式的時間複雜度為線性，接下來是求數組Array最大子數組的遞歸程式：
//求解最大子數組問題的遞歸子程式
struct value find_maximum_subarray(int arr[],int low,int high)
{
//處理一般情況
if(low == high)
{
struct value result;
result.index_left = low;
result.index_right = high;
result.sum = arr[low];
return result;
}
else
{
//進行問題的劃分并遞歸求解
int mid = (low + high)/2;
struct value left_result = find_maximum_subarray(arr,low,mid);
struct value right_result = find_maximum_subarray(arr,mid+1,high);
struct value cross_result = find_max_crossing_subarray(arr,low,mid,high);
if(left_result.sum > right_result.sum && left_result.sum > cross_result.sum)
return left_result;
else if(right_result.sum > left_result.sum && right_result.sum > cross_result.sum)
return right_result;
else
return cross_result;
}
}
這段程式很簡單，處理特殊情況和一般情況，遞歸調用自身，之後再合并解，我們可以想象得到這是一個樹形的結構，從最底層向上
合并結果，最上面即是最後的結果。
完整的程式：
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define MAX 8888
#define MIN -8888
//最大子數組的分治求解算法
//定義類型為結構體類型的傳回結果
struct value
{
int index_left;
int index_right;
int sum;
};
//最大子數組跨越中點的情況
struct value find_max_crossing_subarray(int arr[],int low,int mid,int high)
{
struct value result;
int left_sum = MIN,right_sum = MIN;
int sum;
int max_left,max_right;
//找到左邊數組的最大子數組
sum = 0;
int i;
for(i = mid;i > low-1;i--)
{
sum += arr[i];
if(sum > left_sum)
{
left_sum = sum;
max_left = i;
}
}
//找到右邊數組的最大子數組
sum = 0;
for(i = mid+1;i < high+1;i++)
{
sum += arr[i];
if(sum > right_sum)
{
right_sum = sum;
max_right = i;
}
}
result.index_left = max_left;
result.index_right = max_right;
result.sum = left_sum + right_sum;
return result;
}
//求解最大子數組問題的遞歸子程式
struct value find_maximum_subarray(int arr[],int low,int high)
{
//處理一般情況
if(low == high)
{
struct value result;
result.index_left = low;
result.index_right = high;
result.sum = arr[low];
return result;
}
else
{
//進行問題的劃分并遞歸求解
int mid = (low + high)/2;
struct value left_result = find_maximum_subarray(arr,low,mid);
struct value right_result = find_maximum_subarray(arr,mid+1,high);
struct value cross_result = find_max_crossing_subarray(arr,low,mid,high);
if(left_result.sum > right_result.sum && left_result.sum > cross_result.sum)
return left_result;
else if(right_result.sum > left_result.sum && right_result.sum > cross_result.sum)
return right_result;
else
return cross_result;
}
}
//主程式
void main(void)
{
//設定随即種子
srand((unsigned)time(NULL));
//生成測試數組
int n = 20;
int arr[n];
int i;
printf("原始數組為：\n");
for(i = 0;i<n;i++)
{
arr[i] = rand()%100 - 50;
printf("%4d",arr[i]);
}
printf("\n");
//求得最大子數組
struct value res;
res = find_maximum_subarray(arr,0,n-1);
//列印結果
printf("最大子數組的兩端下标以及子數組和分别為：%4d%4d%4d\n",res.index_left,res.index_right,res.sum);
}
運作結果如下：
再一次:
2.3非遞歸的增量算法
對于求解最大子數組問題，還有另一種思路，這是一種非遞歸的求解算法，求解過程中，處理的部分越來越長，未處
理的部分越來越短，當數組全部處理完之後，整個數組的最大子數組也就找到了。
我們可以從數組的左邊界開始，從左至右處理，記錄到目前為止已經處理過的最大子數組，假設已知arr[0,...,i]
的最大子數組，那麼我們可以線上性時間内求出arr[0,...,i+1]的最大子數組：arr[0,...,i+1]的最大子數組隻有兩
種情況，它要麼是arr[0,...,i]的最大子數組，要麼是某個數組arr[j,...,i+1]，其中0=<j=<i+1,這樣在已知
arr[0,...,i]的最大子數組情況下，就可以線上性時間内求出arr[0,...,i+1]的最大子數組，i自0到n-1,那麼，求解
也就完成了。
對應的C程式如下：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MIN -8888
//求解最大子數組問題的非遞歸算法
//存放結果的結構體
struct value
{
int index_left;
int index_right;
int sum;
};
void main(void)
{
//生成測試數組
int n = 20;
int arr[n];
int i,j;
srand((unsigned)time(NULL));
printf("原始數組為：\n");
for(i = 0;i < n;i++)
{
arr[i] = rand()%100 - 50;
printf("%4d",arr[i]);
}
printf("\n");
//目前最優結果
struct value current_best;
for(i = 0;i < n-1;i++)
{
//i = 0時指派給目前最大數組
if(i==0)
{
current_best.index_left = 0;
current_best.index_right = 0;
current_best.sum = 0;
}
int temp = 0,sum = 0,current_left;
//計算arr[0,...,i+1]的形如arr[j,...,i+1]的最大子數組，然後和之前的arr[0,...,i]的最大子數組(current_best)比較，更新目前最大子數組
for(j = i+1;j > -1;j--)
{
temp += arr[j];
if(temp > sum)
{
sum = temp;
current_left = j;
}
}
//此時，找到了arr[0,...,i+1]的形如arr[j,...,i+1]的最大子數組，現在進行比較
if(sum > current_best.sum)
{
//更新目前最優解
current_best.index_left = current_left;
current_best.index_right = i+1;
current_best.sum = sum;
}
}
//列印結果
printf("數組的最大子數組已經找到，兩端的下标值分别為%4d,%4d,最大子數組的值為%4d\n",current_best.index_left,current_best.index_right,current_best.sum);
}
結果如下：