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

最大子段和算法


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


相关文章:
求最大子段和问题
最大子段和问题_天文/地理_自然科学_专业资料。算法分析设计最大子段解决问题 算法设计与分析实验报告 学院:信息工程与自动化学院 专业:软件工程 141 姓名:赵...
最大子段和问题的算法分析与比较_图文
龙源期刊网 http://www.qikan.com.cn 最大子段和问题的算法分析与比较 作者:陈坚强 来源:《电脑知识与技术》2015 年第 28 期 摘要:随着经济的发展、社会的...
用动态规划算法求解最大子段和
用动态规划算法求解最大子段和_计算机软件及应用_IT/计算机_专业资料。用动态规划算法求解最大子段和算法设计与分析》课程实验报告(一)实验题目 实验时间 一、实...
最大子段和问题改
最大子段和问题改_工学_高等教育_教育专区。计算机算法设计与分析 最大子段和问题 学号:E15301117 E15301098 E15301111 E15301107 姓名:张静 周罕张健夏国峰 ...
最大子段和问题
最大子段和问题_数学_自然科学_专业资料。算法分析及代码 最大字段和问题问题描述: 给定由 n 个整数(包含负整数)组成的序列 a1,a2,...,an,求该序列子 段...
最大子段和问题
最大子段和问题_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载最大子段和问题_计算机软件及应用_IT/计算机_专业资料。《算法设计与分析》 ...
最大子段和问题
目标: 1、熟悉最长最大字段和问题的算法; 2、进一步掌握动态规划算法; 实验任务: 掌握动态规划算法算法的概念和基本思想,分析并掌握最大子段和问题的动态规划算法...
最大子段和问题实验报告
昆明理工大学信息工程与自动化学院学生实验报告( 2011 课程名称:算法设计与分析 年级、 专业、 班 2010 级 计科 102 实验项目名称 最大子段和问题 A.了解□ A...
最大子段和问题
最大子段和问题_计算机软件及应用_IT/计算机_专业资料。最大子段和问题(Maximum Interval Sum) 经典的动态规划问题,几乎所有的算法教材都会提到.本文将分析最大子...
分治法求最大子段和问题
分治法求最大子段和问题_计算机软件及应用_IT/计算机_专业资料。求最大子段和问题。作业要求:程序交.c,和电子版的报告(报告没有格式要求,只要求大家测算算法的...
更多相关标签: