最大子段和n 3算法
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14. int MaxSubseqSum1( int A[], int N ) { int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i MaxSum ) /* 如果刚得到的这个子列和更大 */ MaxSum = ThisSum; /* 则更新结果 */ } /* j循环结束 */ } /* i循环结束 */ return MaxSum; }
最大子段和n 2算法
int MaxSubseqSum2( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( j = i; j
ThisSum += A[j]; /*对于相同的i ，不同的j ，只要在j-1次循环的基础上累加1项即可*/ if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}
最大子段和nlongn 算法(分治)
int maxSum(int a[],int left, int right)
{
int sum = 0;
if(left == right) //如果序列长度为1，直接求解
{
if(a[left] > 0) sum = a[left];
else sum = 0;
}
else
{
int center = (left + right) / 2; //划分
} int leftsum = maxSum(a,left,center); //对应情况1，递归求解 int rightsum = maxSum(a, center + 1, right);//对应情况2， 递归求解 int s1 = 0; int lefts = 0; for(int i = center; i >= left; i--) //求解s1 { lefts += a[i]; if(lefts > s1) s1 = lefts; //左边最大值放在s1 } int s2 = 0; int rights = 0; for(int j = center + 1; j s2) s2 =rights; } sum = s1 + s2; //计算第3钟情况的最大子段和 if(sum
最大子段和动态规划算法
int DY_Sum(int a[],int n)
{
int sum = 0;
int *b = (int *) malloc(n * sizeof(int)); //动态为数组分配空间
b[0] = a[0];
for(int i = 1; i
{
if(b[i-1] > 0)
b[i] = b[i - 1] + a[i];
else
b[i] = a[i];
}
for(int j = 0; j
{
if(b[j] > sum)
sum = b[j];
}
delete []b; //释放内存
return sum;
}
#include
#include
#include
using namespace std;
#define MAX 10000
int BF_Sum(int a[],int n)
{
int max=0;
int sum=0;
int i,j;
for (i=0;i
{
sum=a[i];
for(j=i+1;j
{
if(sum>=max)
{
max=sum;
}
sum+=a[j];
}
}
return max;
}
int maxSum1(int a[],int left, int right)
{
int sum = 0;
if(left == right) //如果序列长度为1，直接求解
{
if(a[left] > 0) sum = a[left];
else sum = 0;
}
else
{
int center = (left + right) / 2; //划分
int leftsum = maxSum1(a,left,center); //对应情况1，递归求解
int rightsum = maxSum1(a, center + 1, right);//对应情况2， 递归求解
int s1 = 0;
int lefts = 0;
for(int i = center; i >= left; i--) //求解s1
{
lefts += a[i];
if(lefts > s1) s1 = lefts; //左边最大值放在s1
}
int s2 = 0;
int rights = 0;
for(int j = center + 1; j
{
rights += a[j];
if(rights > s2) s2 =rights;
}
sum = s1 + s2; //计算第3钟情况的最大子段和
if(sum
}
return sum;
}
int DY_Sum(int a[],int n)
{
int sum = 0;
int *b = (int *) malloc(n * sizeof(int)); //动态为数组分配空间
b[0] = a[0];
for(int i = 1; i
{
if(b[i-1] > 0)
b[i] = b[i - 1] + a[i];
else
b[i] = a[i];
}
for(int j = 0; j
{
if(b[j] > sum)
sum = b[j];
}
delete []b; //释放内存
return sum;
}
int main()
{
int num[MAX];
int i;
const int n = 40;
LARGE_INTEGER begin,end,frequency;
QueryPerformanceFrequency(&frequency);
//生成随机序列
} cout