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

最大子段和算法


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


相关文章:
最大子段和算法
最大子段和算法_学科竞赛_高中教育_教育专区。最大子段和 n3 算法 1. int MaxSubseqSum1( int A[], int N ) 2. { int ThisSum, MaxSum = 0; 3....
最大子段和三种求解方法
1、最大子段和问题的简单算法: 代码: #include<iostream> using namespace std; int MaxSum(int a[],int n,int &besti,int &bestj){ int sum=0; int ...
算法实验3-最大子段和问题实验报告
昆明理工大学信息工程与自动化学院学生实验报告( 2011 课程名称:算法设计与分析 ...一般 □ 开课实验室:信自楼机房 444 姓名 学号 最大子段和问题 吴晟 C.不...
用动态规划算法求解最大子段和
用动态规划算法求解最大子段和_计算机软件及应用_IT/计算机_专业资料。用动态规划算法求解最大子段和算法设计与分析》课程实验报告(一)实验题目 实验时间 一、实...
经典算法最大子序列
经典算法最大子序列_IT/计算机_专业资料。经典算法——求最大子序列和 求最大...} /* * 某段字序列中,含左边界元素的字序列和中的最大值,_maxSubSequenceS...
算法:动态规划解决最大子段和问题
算法:动态规划解决最大子段和问题 /* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题, 然后通过子问题的解得到原问题的解,经过分解的子问题之间并...
最大子段和问题
(3)分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法; (4)比较不同算法的时间性能; (5)给出测试数据,写出程序文档。 求最大子段和问题主要有3种...
最大子段和问题
目标: 1、熟悉最长最大字段和问题的算法; 2、进一步掌握动态规划算法; 实验任务: 掌握动态规划算法算法的概念和基本思想,分析并掌握最大子段和问题的动态规划算法...
求最大子段和问题
最大子段和问题_天文/地理_自然科学_专业资料。算法分析设计最大子段解决问题 算法设计与分析实验报告 学院:信息工程与自动化学院 专业:软件工程 141 姓名:赵...
分治法求最大子段和问题
分治法求最大子段和问题_计算机软件及应用_IT/计算机_专业资料。求最大子段和问题。作业要求:程序交.c,和电子版的报告(报告没有格式要求,只要求大家测算算法的...
更多相关标签:
最大公因子算法 | 算法导论 最大子数组 | 最大子数组和算法 | 最大子数组算法 | 最大完全子图算法 | 最大公共子图算法 | 最大流算法 | 最大子段和 |