走刀口

问题：

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为：

Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20 下面列出了四种计算方式，时间复杂度各逐渐变小，其中动态规划法时间复杂度最小。
[php]
/**
* @brief 最大子段和，穷举法，时间复杂度O(n^3)
*
*/
int MaxSum(int* A, int n)
{
int sum = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
int thissum = 0;
for (int k = i; k <= j; ++k)
{
thissum += A[k];
}
if (thissum > sum)
{
sum = thissum;
}
}
}
return sum;
}
/**
* @brief 最大子段和，穷举法改进，时间复杂度O(n^2)
*
*/
int MaxSumEx(int* A, int n)
{
int sum = 0;
for (int i = 0; i < n; ++i)
{
int thissum = 0;
for (int j = i; j < n; ++j)
{
thissum += A[j];
if (thissum > sum)
{
sum = thissum;
}
}
}
return sum;
}
/**
* @brief 最大子段和，分治法，时间复杂度O(nlogn)
*
* 将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况:
* (1)a[1n]的最大子段和与a[1n/2]的最大子段和相同
* (2)a[1n]的最大子段和与a[n/2n]的最大子段和相同
* (3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n
* T(n)=2T(n/2)+O(n)
* T(n)=O(nlogn)
*/
int MaxSum_DIV(int* A, int left, int right)
{
int sum = 0;
if (left == right)
{
sum = A[left] > 0 ? A[left] : 0;
}
else
{
int center = (left + right) / 2;
int leftMax = MaxSum_DIV(A, left, center);
int rightMax = MaxSum_DIV(A, center + 1, right);

int s1 = 0, leftSum = 0;
for (int i = center; i >= left; –i)
{
leftSum += A[i];
if (leftSum > s1)
{
s1 = leftSum;
}
}
int s2 = 0, rightSum = 0;
for (int j = center + 1; j <= right; ++j)
{
rightSum += A[j];
if (rightSum > s2)
{
s2 = rightSum;
}
}

sum = s1 + s2;
if (leftMax > sum)
{
sum = leftMax;
}
if (rightMax > sum)
{
sum = rightMax;
}
}
return sum;
}
/* @brief 最大子段和，动态规划法，时间复杂度O(n)
* b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。
* 由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:
* b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
* T(n)=O(n)
*/
int MaxSum_DYN(int* A, int n)
{
int sum = 0;
int b = 0;
for (int i = 0; i < n; ++i)
{
if (b > 0)
{
b += A[i];
}
else
{
b = A[i];
}
if (b > sum)
{
sum = b;
}
}
return sum;
}

int main()
{
int A[6] = {-2,11,-4,13,-5,-2};
cout << MaxSum(A, 6) << endl;
cout << MaxSumEx(A, 6) << endl;
cout << MaxSum_DIV(A, 0, 5) << endl;
cout << MaxSum_DYN(A, 6) << endl;
}
[/php]