最大子序列和问题四种解（O）

方法一：

最简单粗暴的想法，以每个点i为起点，以i后面的每个点为终点，求和取最小

for (i = 0 -> n) for (j = i -> n) for (k = i->j) 三重循环，时间复杂度O(N^3)

#include<bits/stdc++.h>
using namespace std;
int MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum,MaxSum = 0;
    for (int i = 0;i < N;++i)
    {
        for (int j = i;j < N;++j)
        {
            ThisSum = 0;
            for (int k = i;k <= j;++k)
                ThisSum += A[k];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}
int main()
{
    int A [8] = {4,-3,5,-2,-1,2,6,-2};
    cout<<MaxSubsequenceSum(A,8)<<endl;
    return 0;
}

方法二：

算是对于方法一的一个优化，在方法一的三个循环中，第三个循环每次都会重复之前的操作，于是将第三个循环省略

（减少重复工作，将需要多次用的计算部分记录下来是一种很重要的优化思想）时间复杂度O(N^2)

#include<bits/stdc++.h>
using namespace std;
int MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum,MaxSum = 0;
    for (int i = 0;i < N;++i)
    {
        ThisSum = 0;
        for (int j = i;j < N;++j)
        {
            ThisSum += A[j];//这里将之前每次计算的结果利用下来
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}
int main()
{
    int A [8] = {4,-3,5,-2,-1,2,6,-2};
    cout<<MaxSubsequenceSum(A,8)<<endl;
    return 0;
}

方法三：

这个问题里用到的分冶方法算是我第一次接触到分冶，之后学习归并排序也是利用分冶，再后来学线段树，感觉线段树也是一种分冶思想

所谓分冶，就是将一个问题分成两个子问题，递归的求解子问题，再将两个子问题的解合并到一起得到整个问题的解

在这个问题中，最大子序列的和可能出现在三处：或者出现在输入数据的左半部，或者出现在后半部，或者跨越中部从而占据左右两部分

对于第三种情况，可以求解左部包含最后一个元素的最大和，右部包含第一个元素的最大和，然后将这两个和加在一起（是否联想到线段树的区间合并了呢？）

例如： 4 -3 5 -2 -1 2 6 -2

前半部的最大和是6（4,-3,5）,后半部的最大和是8（2,6）前半部包含最后一个元素的最大和是4，后半部包含第一个元素的最大和是7

因而最后的结果是4+7 = 11 时间复杂度为O(NlogN)

PS:个人很看重方法三，记得做过很多线段树区间合并的题都用的类似的原理

线段树的区间合并常常是记录包含左端点的值，包含右端点的值，以及区间内的值

随便来个线段树区间合并的例子：点击打开链接

#include<bits/stdc++.h>
using namespace std;
static int MaxSubSum(const int A[],int Left,int Right)
{
    int MaxLeftSum,MaxRightSum;
    int MaxLeftBorderSum,MaxRightBorderSum;
    int LeftBorderSum,RightBorderSum;
    int Center,i;
    if (Left == Right)
    {
        if (A[Left] > 0) return A[Left];
        else return 0;
    }
    Center = (Left+Right)>>1;
    MaxLeftSum = MaxSubSum(A,Left,Center);//递归求解左
    MaxRightSum = MaxSubSum(A,Center+1,Right);//递归求解右
    MaxLeftBorderSum = 0;LeftBorderSum = 0;
    for (i = Center;i >= Left;--i)
    {
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum)
        {
            MaxLeftBorderSum = LeftBorderSum;
        }
    }
    MaxRightBorderSum = 0;RightBorderSum = 0;
    for (i = Center+1;i <= Right;++i)
    {
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum)
        {
            MaxRightBorderSum = RightBorderSum;
        }
    }
    return max(max(MaxLeftSum,MaxRightSum),MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubsequenceSum(const int A[],int N)
{
    return MaxSubSum(A,0,N-1);
}
int main()
{
    int A [8] = {4,-3,5,-2,-1,2,6,-2};
    cout<<MaxSubsequenceSum(A,8)<<endl;
    return 0;
}

方法四：

如果没有方法四，我们可以很清晰的看到递归的好处，但是美丽的DP思想让方法四完美到无懈可击

在求最大子序列和的时候，我们注意到，只要是正数就可以为我们的结果增益，而负数则舍弃

时间复杂度O(N)，同时代码不长

#include<bits/stdc++.h>
using namespace std;
int MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum = 0, MaxSum = 0;
    for (int i = 0;i < N;++i)
    {
        ThisSum += A[i];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;
    }
    return MaxSum;
}
int main()
{
    int A [8] = {4,-3,5,-2,-1,2,6,-2};
    cout<<MaxSubsequenceSum(A,8)<<endl;
    return 0;
}

运用：点击打开链接

参考资料:

《数据结构与算法分析 -- C语言描述》

PS：

当初看一位大神的成长之路就推荐了这本书，大神说看到书中将一个O(N^3)的算法一路杀到O(N)，当时心中那个崇拜之情。。。想来大神说的就是这个例子

后来我也买了这本书，可惜看之前已经学了不少算法，所以对此没有太强烈的感觉，但是还是能深刻体会到算法的强大魅力

大神的成神之路：我的算法学习之路

秒客网

最大子序列和问题四种解（O）

相关文章