分治法策略解决最大子数组问题

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

问题描述

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)

程序范例

#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;
}

总结

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

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


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

参考文章:

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


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。