(时间复杂度为 Θ（nlgn） )的C++方法实现：LZ是用Qt进行编译的，所以就加上了Qt的头文件，如果不需要的话，可以直接删除，最后返回return 0；就可以了。 采用递归，也就是函数内部调用自己的时候要加上c++11的特性。
#include <QCoreApplication> #include <iostream> #include <cmath> using namespace std; struct maximum_subarray{ int index_low; int index_high; int max_sum; }; maximum_subarray find_max_crossing_subarray(int A[], int low, int mid, int high); maximum_subarray find_maximum_subarray(int A[], int low, int high); int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); int array[16] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; cout << "the original array is " << endl; for (int i = 0; i < 16; i++) { cout << " "<< array[i]; } cout << endl; int low = 0, high = 15; maximum_subarray max_sub; max_sub = find_maximum_subarray(array, low, high); cout <<"the maximum subarray is " << endl; for (int i = max_sub.index_low; i < max_sub.index_high; i++) { cout << " " << array[i]; } cout << endl; cout << "the value of the maximum subarray is " << max_sub.max_sum << endl; return a.exec(); } maximum_subarray find_max_crossing_subarray(int A[], int low, int mid, int high) { maximum_subarray cs_max; int left_sum = INT_MIN; int sum = 0, max_left = 0; for (int i = mid; i >= low; i--) { sum = sum + A[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } int right_sum = INT_MIN; sum = 0; int max_right = 0; for (int i = mid+1; i <= high; i++) { sum = sum + A[i]; if (sum > right_sum) { right_sum = sum; max_right = i; } } cs_max.index_low = max_left; cs_max.index_high = max_right; cs_max.max_sum = left_sum + right_sum; return cs_max; } maximum_subarray find_maximum_subarray(int A[], int low, int high) { maximum_subarray ms_0; maximum_subarray ms_l, ms_r, ms_cs; if (high == low) { ms_0.index_low = low; ms_0.index_high = high; ms_0.max_sum = A[low]; return ms_0; } else { int mid = floor((low + high) / 2); ms_l = find_maximum_subarray(A, low, mid); ms_r = find_maximum_subarray(A, mid+1, high); ms_cs = find_max_crossing_subarray(A, low, mid, high); if ((ms_l.max_sum >= ms_r.max_sum) && (ms_l.max_sum >= ms_cs.max_sum)) return ms_l; else if ((ms_r.max_sum >= ms_l.max_sum) && (ms_r.max_sum >= ms_cs.max_sum)) return ms_r; else return ms_cs; } }最后显示如图所示O(∩_∩)O哈哈~
