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

Skyed.blue

于 2019-11-14 23:27:40 发布

阅读量501

点赞数

分类专栏：算法 pta-竞赛动态规划

本文链接：https://blog.csdn.net/Skyed_blue/article/details/103076147

版权

本文介绍了三种解决最大连续子列和问题的方法：分治法，动态规划和在线处理。分治法通过递归左、右子树找到可能的最大连续区间；动态规划通过dp数组记录包含当前位置的最大子列和；在线处理根据当前区间和决定是否改变区间起点，以保持最大子列和。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目地址在此

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

方法一：分治 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 =