比较经典的算法问题,能够很好的体现动态规划的实现,以一点“画龙点睛” 大大精简了算法复杂度,且实现简单。本文中实现了4种:
一般 maxSubSequenceSum0 O(n^3)
简单优化过的算法 maxSubSequenceSum1 O(n^2)
分治法优化的算法 maxSubSequenceSum2 O(n*log(n))
动态规划的算法 maxSubSequenceSum3 O(n)
#include <math.h>
#include "mymath.h"
/*
* 计算序列的某段子序列的和,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[left];
for (i = left; i <= right; i++)
{
sum += a[i];
if (sum > maxSum)
{
maxSum = sum;
}
}
return maxSum;
}
/*
* 某段字序列中,含右边界元素的字序列和中的最大值,_maxSubSequenceSum2中使用
*/
static int _maxRightBoderSubSequenceSum(int a[], int left, int right)
{
int i;
int sum = 0;
int maxSum = a[right];
for (i = right; i >= left; i--)
{
sum += a[i];
if (sum > maxSum)
{
maxSum = sum;
}
}
return maxSum;
}
/*
* 求序列某段子序列中子序列和最大值
*/
static int _maxSubSequenceSum2(int a[], int left, int right)
{
int center;
int leftMaxSum;
int rightMaxSum;
int maxLeftBorderSum;
int maxRightBorderSum;
/* 递归终止条件 */
if (left == right)
{
#include "mymath.h"
/*
* 计算序列的某段子序列的和,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[left];
for (i = left; i <= right; i++)
{
sum += a[i];
if (sum > maxSum)
{
maxSum = sum;
}
}
return maxSum;
}
/*
* 某段字序列中,含右边界元素的字序列和中的最大值,_maxSubSequenceSum2中使用
*/
static int _maxRightBoderSubSequenceSum(int a[], int left, int right)
{
int i;
int sum = 0;
int maxSum = a[right];
for (i = right; i >= left; i--)
{
sum += a[i];
if (sum > maxSum)
{
maxSum = sum;
}
}
return maxSum;
}
/*
* 求序列某段子序列中子序列和最大值
*/
static int _maxSubSequenceSum2(int a[], int left, int right)
{
int center;
int leftMaxSum;
int rightMaxSum;
int maxLeftBorderSum;
int maxRightBorderSum;
/* 递归终止条件 */
if (left == right)
{