最大子数组和——动态规划法

本文主要是介绍最大子数组和——动态规划法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、总结上一篇方法

       上一篇求解最大子数组用的是暴力求解法，把所有可能的子数组和求出来，然后比较得出最大的子数组和，这方法也是最容易想出来的，编程比较容易，感兴趣的同学可以看我的上一篇博客。

2、基于动态规划的最大子数组求和问题

        由于暴力求解的复杂度为O(n**3)，确实有点大，那么不妨采用动态规划法求解，主要思路也很简单明了，我们假设最大和子数组由两部分组成，一个是前向和sum，另一个部分就是前向和sum的下一个元素，如果sum的值小于0就意味着它不可能成为最大子数组的一部分了，因此必须舍弃之前的sum，重新定义新的sum，这个sum的起始元素就是之前sum和序列的下一个元素。动态规划法简洁明了，时间复杂度仅为O(n)，减少了求解次数。

3、代码样例

arr = [1,-2,3,<

这篇关于最大子数组和——动态规划法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---