最大连续子列和(多种方法)

本文主要是介绍最大连续子列和(多种方法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址在此

经典问题，求最大连续区间和。
暴力的方法就不说了。
这里说三种方法：分治，动态规划，在线处理。

方法一：分治 O(nlgn)

要求[1,n]的最大连续区间和，可以将区间分成[l,mid],[mid,r]，即左右两半。此时，有三种情况。
1：该连续区间全部在左半部分。
2：该连续区间全部在右半部分。
3：该连续区间出现在中间，即a[mid]在区间里。
对于情况1，2就是递归左子树，右子树即可。
对于情况3，我们已经确定一个条件：a[mid]必定在该连续区间。因此我们只需要从mid出发，mid->l求出左半边的最大连续区间和，mid+1->r求出右半边的最大连续区间和，最后加起来就是情况3。
我们取这三种情况的最大值即可。

#include <iostream>
using namespace std;int a[100010];int divide(int l, int r)
{if(l < r)	{int mid = (l+r)/2;int sum1 = divide(l,mid-1);	//最大区间和完全在左边 int sum2 = divide(mid+1,r);	//最大区间和完全在右边 int maxL = 0, maxR = 0, sumL =

这篇关于最大连续子列和(多种方法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---