当前位置:首页 >> 学科竞赛 >>

最大子段和算法


最大子段和 n3 算法
1. int MaxSubseqSum1( int A[], int N ) 2. { int ThisSum, MaxSum = 0; 3. int i, j, k; 4. for( i = 0; i < N; i++ ) { /* i 是子列左端位置 */ 5. for( j = i; j < N; j++ ) { /* j 是子

列右端位置 */ 6. ThisSum = 0; /* ThisSum 是从 A[i]到 A[j]的子列和 */ 7. for( k = i; k <= j; k++ ) 8. ThisSum += A[k]; 9. if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */ 10. MaxSum = ThisSum; /* 则更新结果 */ 11. } /* j 循环结束 */ 12. } /* i 循环结束 */ 13. return MaxSum; 14. }

最大子段和 n2 算法
int MaxSubseqSum2( int A[], int N ) { int ThisSum, MaxSum = 0; int i, j; for( i = 0; i < N; i++ ) { /* i 是子列左端位置 */ ThisSum = 0; /* ThisSum 是从 A[i]到 A[j]的子列和 */ for( j = i; j < N; j++ ) { /* 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 <= right; j++)//求解 s2 { rights += a[j]; if(rights > s2) s2 =rights; } sum = s1 + s2; //计算第 3 钟情况的最大子段和 if(sum < leftsum) sum = leftsum; //合并,在 sum、leftsum、rightsum 中取最大值 if(sum < rightsum) sum = rightsum; } 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 < n; i++) { if(b[i-1] > 0) b[i] = b[i - 1] + a[i]; else b[i] = a[i]; } for(int j = 0; j < n; j++) { if(b[j] > sum) sum = b[j]; } delete []b; //释放内存 return sum; }

//动态为数组分配空间

完整测试程序:
#include<iostream> #include<time.h> #include<Windows.h> 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<n-1;i++) { sum=a[i]; for(j=i+1;j<n;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 <= right; j++)//求解 s2 { rights += a[j]; if(rights > s2) s2 =rights; } sum = s1 + s2; //计算第 3 钟情况的最大子段和 if(sum < leftsum) sum = leftsum; //合并,在 sum、leftsum、rightsum 中取最大值 if(sum < rightsum) sum = rightsum; } 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 < n; i++) { if(b[i-1] > 0) b[i] = b[i - 1] + a[i]; else b[i] = a[i]; } for(int j = 0; j < n; 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<<"生成随机序列:"; srand(time(0)); for(int i = 0; i < n; i++) { if(rand() % 2 == 0) num[i] = rand(); else num[i] = (-1) * rand(); if(n < 100) cout<<num[i]<<" "; } cout<<endl; //蛮力法// cout<<"\n 蛮力法:"<<endl; cout<"最大字段和:"; QueryPerformanceCounter(&begin); cout<<BF_Sum(num,n)<<endl; QueryPerformanceCounter(&end); cout<<"时间:" <<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart <<"s"<<endl; cout<<"\n 分治法:"<<endl; cout<"最大字段和:"; QueryPerformanceCounter(&begin); cout<<maxSum1(num,0,n)<<endl; QueryPerformanceCounter(&end); cout<<"时间:" <<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart <<"s"<<endl; cout<<"\n 动态规划法:"<<endl; cout<"最大字段和:"; QueryPerformanceCounter(&begin); cout<<DY_Sum(num,n)<<endl; QueryPerformanceCounter(&end); cout<<"时间:" <<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart <<"s"<<endl; system("pause"); return 0; }


相关文章:
算法:动态规划解决最大子段和问题
算法:动态规划解决最大子段和问题 /* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题, 然后通过子问题的解得到原问题的解,经过分解的子问题之间并...
算法.最大子段和
〖题目描述〗 在一个一维数组里找出连续的几个数,使数的总和最大。 计算最大子段和的 5 种算法(c 实现) #include<iostream.h> #define sum 21 int b[sum...
最大子段和问题改
最大子段和问题改_工学_高等教育_教育专区。计算机算法设计与分析 最大子段和问题 学号:E15301117 E15301098 E15301111 E15301107 姓名:张静 周罕张健夏国峰 ...
最大子段和问题
(3)分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法; (4)比较不同算法的时间性能; (5)给出测试数据,写出程序文档。 求最大子段和问题主要有3种...
分治法求最大子段和问题
分治法求最大子段和问题_计算机软件及应用_IT/计算机_专业资料。求最大子段和问题。作业要求:程序交.c,和电子版的报告(报告没有格式要求,只要求大家测算算法的...
最大子段和问题实验报告
昆明理工大学信息工程与自动化学院学生实验报告( 2011 课程名称:算法设计与分析 年级、 专业、 班 2010 级 计科 102 实验项目名称 最大子段和问题 A.了解□ A...
算法分析习题参考答案第五章
2) 试用分治算法最大子段和问题,并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质,并设计一个动态规划算法最大子段和问题。分析...
算法分析作业_图文
D、回溯法 18.实现大整数的乘法是利用的算法( A、贪心法 B、动态规划法 C、分治策略 B C、贪心法 19. 实现最大子段和利用的算法是( A、分治策略 B、...
算法分析复习题目及答案
算法分析复习题目及答案_工学_高等教育_教育专区。一、选择题 1、二分搜索算法...实现最大子段和利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心...
求最大子段和C.C++程序实现及其效率分析
最大子段和 1) 2) 3) 简单蛮力算法的程序实现及其效率分析, 分治法求解的程序实现及其效率分析,包括效率分析过程的递归求解。 动态规划法求解的程序实现及其效...
更多相关标签: