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

最大子段和算法


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


赞助商链接
相关文章:
最大子段和问题的算法分析与比较_图文
最大子段和问题的算法分析与比较 - 龙源期刊网 http://www.qikan.com.cn 最大子段和问题的算法分析与比较 作者:陈坚强 来源:《电脑知识与技术》2015 年第 ...
最大子段和问题
目标: 1、熟悉最长最大字段和问题的算法; 2、进一步掌握动态规划算法; 实验任务: 掌握动态规划算法算法的概念和基本思想,分析并掌握最大子段和问题的动态规划算法...
分治法求最大子段和问题
分治法求最大子段和问题_计算机软件及应用_IT/计算机_专业资料。求最大子段和问题。作业要求:程序交.c,和电子版的报告(报告没有格式要求,只要求大家测算算法的...
最大子段和动态规划法
算法实验3-最大子段和问题... 11页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
最大子段和三种求解方法
1、最大子段和问题的简单算法: 代码: #include<iostream> using namespace std; int MaxSum(int a[],int n,int &besti,int &bestj){ int sum=0; int...
算法:动态规划解决最大子段和问题
算法:动态规划解决最大子段和问题 /* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题, 然后通过子问题的解得到原问题的解,经过分解的子问题之间并...
3.算法-求最大子段和问题-实验报告格式
3.算法-求最大子段和问题-实验报告格式_计算机软件及应用_IT/计算机_专业资料。格式昆明理工大学信息工程与自动化学院学生实验报告( 2014 课程名称:算法设计与分析...
算法.最大子段和
〖题目描述〗 在一个一维数组里找出连续的几个数,使数的总和最大。 计算最大子段和的 5 种算法(c 实现) #include<iostream.h> #define sum 21 int b[sum...
最大子段和问题课程设计报告格
最大子段和问题课程设计报告格_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档最大子段和问题课程设计报告格_工学_高等教育_教育专区。《算法设计...
最大子段和问题
最大子段和问题 - 《算法设计与分析》 课程设计报告 题 目: 最大子段和问题 信息科学与工程学院 软件工程 1201 班 院 (系) : 专业班级: 20 14 年 12 ...
更多相关标签: