## 问题描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

O(nlgn)

## 程序范例

[code lang=”cpp”]
#include <iostream>
#include <cstdlib>

using namespace std;

int find_max_crossing_subarray(int* a, int low, int mid, int high)
{
int sum = 0;
int left_sum = 0;
int right_sum = 0;

for (int i = mid; i >= low; i–) {
left_sum += a[i];
if (left_sum >= sum) {
sum = left_sum;
}
}

right_sum = sum;
for (int i = mid + 1; i <= high; i++) {
right_sum += a[i];
if (right_sum >= sum) {
sum = right_sum;
}
}
return sum;
}

int find_maximum_subarray(int* a, int low, int high)
{
//std::cout<<"find_maximum_subarray"<<std::endl;
//std::cout<<"the low"<<low<<"the high"<<high<<std::endl;
if (low == high) {
return a[low];
} else {
int mid = (low + high)>>1;
//std::cout<<"mid"<<mid<<std::endl;
int left_sum = 0;
int right_sum = 0;
int cross_sum = 0;
left_sum = find_maximum_subarray(a, low, mid);
//std::cout<<"left_sum"<<left_sum<<std::endl;
right_sum = find_maximum_subarray(a, mid + 1, high);
//std::cout<<"right_sum"<<right_sum<<std::endl;
cross_sum = find_max_crossing_subarray(a, low, mid, high);
//std::cout<<"cross_sum"<<cross_sum<<std::endl;
if (left_sum > right_sum && left_sum > cross_sum) {
return left_sum;
} else if(right_sum > left_sum && right_sum > cross_sum) {
return right_sum;
} else {
return cross_sum;
}
}
}

int main() {
int a[] = {2, 4, -10, 6, 30, 4, 3, -10, 32, 10};
//std::cout<<find_maximum_subarray(a, 0, 9)<<std::endl;
return 0;
}
[/code]

## 总结

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.