文章目录

问题描述

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.

问题来自于Leetcode:Maximum Subarray

解决方式

利用分治策略来解决最大子数组问题

时间复杂度

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]

总结

分治法的主要细想即三部曲:分解(divide)、解决(conquer)与合并(combine)。掌握大致这三个步骤,再加上对递归的使用,即可利用分治策略来解决一些问题。这样往往时间复杂度会比暴力解决问题效率高的多。

对于分治法在排序上的经典运用可以参阅:分治法的经典运用归并排序(Merge Sort)


文章来源:胡旭博客 => 分治法策略解决最大子数组问题

参考文章:

转载请注明出处,违者必究!

Share:

Leave a Reply

Your email address will not be published.

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