最大子段和算法

最大子段和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


© 2024 实用范文网 | 联系我们: webmaster# 6400.net.cn