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

最大子段和算法


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


相关文章:
最大子段和(三种算法) 的MATLAB求解
最大子段和(三种算法) 1、蛮力法 function [sum,besti,bestj]=MaxSum(v,n)%%蛮力法 sum=0; for i=1:n thisSum=0; for j=i:n thisSum=thisSum+v...
分治法求最大子段和问题
分治法求最大子段和问题_计算机软件及应用_IT/计算机_专业资料。求最大子段和问题。作业要求:程序交.c,和电子版的报告(报告没有格式要求,只要求大家测算算法的...
算法分析习题参考答案第五章
2) 试用分治算法最大子段和问题,并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质,并设计一个动态规划算法最大子段和问题。分析...
算法分析作业_图文
D、回溯法 18.实现大整数的乘法是利用的算法( A、贪心法 B、动态规划法 C、分治策略 B C、贪心法 19. 实现最大子段和利用的算法是( A、分治策略 B、...
算法分析与设计实验报告-最大子段和、0-1背包问题
实验报告课程 学号 计算机算法设计与分析 姓名 实验名称 最大子段和、0-1 背包问题 实验日期: 实验二一.实验目的 最大子段和、0-1 背包问题 (1) 学习最大...
算法习题
(5 分) 2、 由流水作业调度问题的最优子结构性质可知, T (N, 0) = min{ai+T(N-{i},bi)}(1=<i<=n) (5 分) 3、最大子段和问题的简单算法(...
算法分析复习题目及答案
( A、分支界限法 B、动态规划法 D、回溯法 44.贪心算法与动态规划算法的主要区别是( A、最优子结构 优解 45. 实现最大子段和利用的算法是( A、分治策略 ...
算法分析复习题目及答案
算法分析复习题目及答案_工学_高等教育_教育专区。一、选择题 1、二分搜索算法...实现最大子段和利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心...
算法分析复习题目及答案16-12-10
算法分析复习题目及答案16-12-10_IT认证_资格考试/认证_教育专区。一。选择题...实现最大子段和利用的算法是( A、分治策略 B、动态规划法 46.优先队列式分支...
分治法求最大子段和首先将问题
分治法求最大子段和首先将问题 1、基本思想: 用分治法求最大子段和首先将...(n),所以有递推公式为: 1 T(n)= 2T(n/2)+n n>1 所以,分治算法的...
更多相关标签:
最大公因子算法 | 最大完全子图算法 | 分治算法 最大子序列 | 求最大子串算法 | 最大子数组和算法 | 贪心算法 最大子数组 | 最大子序列和联机算法 | 算法导论 最大子数组 |