最大连续和有关问题及其拓展

最大连续和问题及其拓展

问题描述：
有一串数字，可正可负也可为0，连续两个或多个数字组成了一个子序列，每个子序列都有一个和，求出所有子序列中和最大的一个。

例如:
        输入的数组为3 6 -7 -1 4 3 -2 -5 10 -3,则和最大的子序列为3 6 -7 -1 4 3 -2 -5 10,最大和为11.

        关于写这篇文章,纯属自己在刷题过程中发现有不少题目是从这个问题上面演变而来,所以打算写出来做个记录.

        最大连续和问题,O(n^2)的解法是很容易想到的,但如果n是100W级别的,那这个算法的效率就相当的

底下了,所以,我们需要更好的解法.既然O(n^2)解决不了,那么,我们能不能把时间复杂度优化为O(nlgn).

由于时间复杂度里面出现lgn,所以得往二分上面去想,试想一下,如果一个序列S,从中将其分成两段L,R,

那么,原序列S的最大连续和跟L和R的最大连续和有什么关系?您可能会觉得S的最大连续和就是L和R

的最大连续和中最大的那个值,其实不然,有种情况被您漏掉了:可能L的右端+R的左端拼接出来的最大

和大于前所说的最大连续和,具体的可以考虑这组数据S={1,2,3,4,5,6},L={1,2,3},R={4,5,6},这里我们

是不能由L和R的最大连续和得出S的最大连续和,我们得记录用了L最右端的那个元素能组成的最大

连续和和用了R最左端的那个元素能组成的最大连续和,然后两者相加,最后,三者取最大值,这样我们

才能得出S的最大连续和.其实,这个问题类似线段树的区间合并问题,这里就不做过多的解释.

下面是O(nlgn)解法的代码:

int solve(int l,int r,int *arr)
{
    if(l == r)
        return arr[l];
    int m = l + ( r - l ) / 2 ;
    int l_max = solve(l,m,arr);
    int r_max = solve(m+1,r,arr);
    int l_tmp = arr[m],r_tmp = arr[m+1];
    for(int i=m,sum=0;i>=l;--i)
        l_tmp = max(l_tmp,sum +=arr[i]);
    for(int j=m+1,sum=0;j<=r;++j)
        r_tmp = max(r_tmp,sum +=arr[j]);
    return max(l_tmp+r_tmp,max(l_max,r_max));
}

对于这个问题,用DP也能解决,时间复杂度为O(n).设定状态为:

dp[i]:表示选了第i个元素能组成的最大连续和是多少.
dp[i] = max(dp[i-1]+arr[i],arr[i]).(arr[i]表示数组第i号元素).

当然了,如果用这种dp状态和状态的转移方程,时间复杂度虽然是O(n),但有个常系数2,其实,我们只用稍稍

的将上面的状态和状态转移方程做个更改,就能将常系数变成1.可以如下定义状态以及状态转移方程:

dp[i]:表示前i个数的能组成的最大连续和是多少.
dp[i] = max(dp[i-1],tmp = max(tmp+arr[i],arr[i])),其中tmp为选了第i-1号元素能组成的最大连续和.

这样,我们就能以严格的O(n)解决这个问题了,具体实现代码如下:

//MAX_N为数组的最大元素个数
int dp[MAX_N];
int solve(int n,int *arr)
{
    int tmp = dp[0] = arr[0];
    for(int i=1;i<n;++i)
        dp[i] = max(dp[i-1],tmp = max(tmp+arr[i],arr[i]));
    return dp[n-1];
}

注:其实,上述程序的dp数组是不用开的,用个变量就可以替代的,这样的话,如果是在输入时做处理,

空间复杂度能达到O(1).

下面我们来看看这个问题的一些拓展.

拓展一

给定一个含有n个元素的集合A={a1,a2,....,an},我们定义函数d(A)如下所示:

最大连续和有关问题及其拓展

数据范围:n<=50000,|ai|<=10000

这道题目与最大连续和问题的本质是一样的,从d(A)的定义中,我们可以发现d(A)是由两段子序列的

最大连续和拼接而来,而两子序列的分界点不确定,只能枚举[2,n-1]区间中的点作为分界点,这里有个问

题,当枚举到某个分界点i时,是否需要每次都去求[i,n]的最大连续和吗?其实,可以不用每次都去求,事先

求出[1,n]的最大连续和并作记录,然后枚举分界点的时候,直接查询就行了.所以总的时间复杂度为O(n).

具体实现的代码:

#include<stdio.h>
#include<algorithm>
#define MAX_N 50090
using namespace std;
int arr[MAX_N],dp[MAX_N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,tmp ;
        scanf("%d",&n);
        for(int i=0;i<n;++i)
            scanf("%d",arr+i);
        dp[0] = tmp = arr[0];
        for(int i=1;i<n;++i)
            dp[i] = max(dp[i-1],tmp=max(tmp+arr[i],arr[i]));
        int ans = dp[n-2] + arr[n-1];
        int t_max = tmp = arr[n-1];
        for(int i=n-2;i>0;--i)
        {
            t_max = max(t_max,tmp = max(tmp+arr[i],arr[i]));
            ans = max(t_max+dp[i-1],ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}

题目地址:http://poj.org/problem?id=2479

拓展二

给定一个N*N的矩阵,矩阵的和定义为矩阵中所有元素相加(一个矩阵存在着很多的子矩阵),现要求

你找出这N*N的矩阵中最大的子矩阵的和.数据范围:N<=100,矩阵中的元素的绝对值<=127.
例如:

0	-2	-7	0
9	2	-6	2
-4	1	-4	1
-1	8	0	-2

上面的这样一个矩阵,由于9 2 -4 1 -1 8这个子矩阵的和最大,所以该输出15(9+2-4+1-1+8).

之前讨论的问题都是一维的数组元素,而现在问题拓展成两维的了,貌似就不能用上面的方法了.其实,

这个问题也是从前面的问题演变而来,对于子矩阵的求和,我们可以将一列元素的和看成是一个元

素(其值为相应列元素的和),这样,子矩阵求和就转化为一维的了,而我们只用去枚举子矩阵的高就

可以了,时间复杂度为O(n^3).

具体的代码见下:

#include<stdio.h>
#include<algorithm>
#define MAX_N 120
using namespace std;
int sum[MAX_N][MAX_N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&sum[i][j]);
            sum[i][j] +=sum[i-1][j];
        }
    }
    int res = -1000;
    for(int i=1;i<=n;++i)
    {
        for(int j = 0;j+i<=n;++j)
        {
            int tmp =0 ;
            for(int k=1,tmp1;k<=n;++k)
            {
                tmp1 =sum[i+j][k] - sum[i-1][k] ;
                res = max(res,tmp = max(tmp+tmp1,tmp1));
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

题目链接地址:http://poj.org/problem?id=1050

如果您在阅读过程中发现代码有问题或者有更好的解法,请在下面留下您的足迹.

最大连续和有关问题及其拓展

相关推荐