经典算法最大子序列.docx

经典算法——求最大子序列和
比较经典的算法问题,能够很好的体现动态规划的实现,以一点“画龙点睛” 大大精简了算法复杂度,且实现简单。本文中实现了4种:
一般 maxSubSequenceSum0  O(n^3)
简单优化过的算法 maxSubSequenceSum1  O(n^2)
分治法优化的算法 maxSubSequenceSum2  O(n*log(n))
动态规划的算法 maxSubSequenceSum3  O(n)
#include <>
#include ""
/*
 * 计算序列的某段子序列的和,maxSubSequenceSum0使用
 */
static int subSequenceSum(int a[], int left, int right)
{
    int i, sum = 0;
    for (i = left; i <= right; i++)
    {
        sum = sum + a[i];
    }
    return sum;
}
/*
 * 三层遍历求子序列和的最大值,算法复杂度O(n^3)
 */
int maxSubSequenceSum0(int a[], int len)
{
    int i, j;
    int curSum; /* 当前序列和 */
    int maxSum; /* 最大序列和 */
    /* 初始化最大子序列和为序列第一个元素 */
    maxSum = a[0];
    /* 第一层循环定义子序列起始位置 */
    for (i = 0; i < len; i++)
    {
        /* 起始位置为i,初始化当前和为0 */
        curSum = 0;
        /* 第二层循环定义子序列结束位置 */
        for (j = i; j < len; j++)
        {
            /* 第三层循环在函数sumSubseqence中,计算子序列和 */
            curSum = subSequenceSum(a, i, j);
            /* 与最大子序列和比较,更新最大子序列和 */
            if (curSum > maxSum)
            {
                maxSum = curSum;
            }
        }
    }
    return maxSum;
}
/*
 * 双层遍历求子序列和的最大值,算法复杂度O(n^2)
 */
int maxSubSequenceSum1(int a[], int len)
{
    int i, j;
    int curSum; /* 当前序列和 */
    int maxSum; /* 最大序列和 */
    /* 初始化最大子序列和为序列第一个元素 */
    maxSum = a[0];
    /* 外层循环定义子序列起始位置 */
    for (i = 0; i < len; i++)
    {
        /* 起始位置为i,初始化当前和为0 */
        curSum = 0;
        /* 内层循环定义子序列结束位置 */
        for (j = i; j < len; j++)
        {
            /* 计算子序列和,并与最大子序列和比较,更新最大子序列和 */
            curSum = curSum + a[j];
            /* 与最大子序列和比较,更新最大子序列和 */
            if (curSum > maxSum)
            {
                maxSum = curSum;
            }
        }
    }
    return maxSum;
}
/*
 * 某段字序列中,含左边界元素的字序列和中的最大值,_maxSubSequenceSum2中使用
 */
static int _maxLeftBoderSubSequenceSum(int a[], int left, int right)
{
    int i;
    int sum = 0;
    int maxSum = a[lef