动态规划解决最大子数组问题

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

支付宝微  信

问题

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(n)

程序范例

#include <iostream>
int solve(int* a, int length) {
    int sum = a[0];
    for (int i = 1; i < length; i++) {
        if (a[i] < a[i] + a[i - 1]) {
            a[i] = a[i] + a[i - 1];
        }
        if (sum < a[i]) {
            sum = a[i];
        }
    }
    return sum;
}

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

总结

能够利用动态规划思路来解决的问题的特性主要有两点:

  1. 重叠子问题(overlapping sub-problem)- 即当前状态的解取决于上一个状态的解
  2. 最优子结构(optimal sub-structure)- 求的解释问题的最有子解

文章来源:胡旭博客 => 动态规划解决最大子数组问题

参考文章:算法导论(p74 练习题4.1-5)

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


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


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

发表评论

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