http://blog.csdn.net/liufeng_king/article/details/8632430

1、最大子段和问题

     问题定义：对于给定序列a1,a2,a3……an,寻找它的某个连续子段，使得其和最大。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。

(1)枚举法求解

枚举法思路如下：

以a[0]开始: {a[0]}, {a[0],a[1]},{a[0],a[1],a[2]}……{a[0],a[1],……a[n]}共n个

以a[1]开始: {a[1]}, {a[1],a[2]},{a[1],a[2],a[3]}……{a[1],a[2],……a[n]}共n-1个

……

以a[n]开始:{a[n]}共1个

一共(n+1)*n/2个连续子段，使用枚举，那么应该可以得到以下算法：
     具体代码如下：

  1. //3d4-1 最大子段和问题的简单算法
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSum(int n,int *a,int& besti,int& bestj);
  6. int main()
  7. {
  8. int a[] = {-2,11,-4,13,-5,-2};
  9. for(int i=0; i<6; i++)
  10. {
  11. cout<<a[i]<<" ";
  12. }
  13. int besti,bestj;
  14. cout<<endl;
  15. cout<<"数组a的最大连续子段和为：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;
  16. return 0;
  17. }
  18. int MaxSum(int n,int *a,int& besti,int& bestj)
  19. {
  20. int sum = 0;
  21. for(int i=0; i<n; i++)//控制求和起始项
  22. {
  23. for(int j=i; j<n; j++)//控制求和结束项
  24. {
  25. int thissum = 0;
  26. for(int k=i; k<=j; k++)//求和
  27. {
  28. thissum += a[k];
  29. }
  30. if(thissum>sum)//求最大子段和
  31. {
  32. sum = thissum;
  33. besti = i;
  34. bestj = j;
  35. }
  36. }
  37. }
  38. return sum;
  39. }

从这个算法的三个for循环可以看出，它所需要的计算时间是O(n^3)。事实上，如果注意到，则可将算法中的最后一个for循环省去，避免重复计算，从而使算法得以改进。改进后的代码如下：

  1. //3d4-2 最大子段和问题的避免重复的简单算法
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSum(int n,int *a,int& besti,int& bestj);
  6. int main()
  7. {
  8. int a[] = {-2,11,-4,13,-5,-2};
  9. for(int i=0; i<6; i++)
  10. {
  11. cout<<a[i]<<" ";
  12. }
  13. int besti,bestj;
  14. cout<<endl;
  15. cout<<"数组a的最大连续子段和为：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;
  16. return 0;
  17. }
  18. int MaxSum(int n,int *a,int& besti,int& bestj)
  19. {
  20. int sum = 0;
  21. for(int i=0; i<n; i++)//控制求和起始项
  22. {
  23. int thissum = 0;
  24. for(int j=i; j<=n; j++)//控制求和结束项
  25. {
  26. thissum += a[j];//求和
  27. if(thissum>sum)
  28. {
  29. sum = thissum;
  30. besti = i;
  31. bestj = j;
  32. }
  33. }
  34. }
  35. return sum;
  36. }

(2)分治法求解

分治法思路如下：

将序列a[1:n]分成长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大字段和，则a[1:n]的最大子段和有三中情形：

[1]、a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；

[2]、a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；

[3]、a[1:n]的最大字段和为，且1<=i<=n/2,n/2+1<=j<=n。

可用递归方法求得情形[1],[2]。对于情形[3],可以看出a[n/2]与a[n/2+1]在最优子序列中。因此可以在a[1:n/2]中计算出，并在a[n/2+1:n]中计算出。则s1+s2即为出现情形[3]时的最优值。

具体代码如下：

  1. //3d4-1 最大子段和问题的分治算法
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSubSum(int *a,int left,int right);
  6. int MaxSum(int n,int *a);
  7. int main()
  8. {
  9. int a[] = {-2,11,-4,13,-5,-2};
  10. for(int i=0; i<6; i++)
  11. {
  12. cout<<a[i]<<" ";
  13. }
  14. cout<<endl;
  15. cout<<"数组a的最大连续子段和为:"<<MaxSum(6,a)<<endl;
  16. return 0;
  17. }
  18. int MaxSubSum(int *a,int left,int right)
  19. {
  20. int sum = 0;
  21. if(left == right)
  22. {
  23. sum = a[left]>0?a[left]:0;
  24. }
  25. else
  26. {
  27. int center = (left+right)/2;
  28. int leftsum = MaxSubSum(a,left,center);
  29. int rightsum = MaxSubSum(a,center+1,right);
  30. int s1 = 0;
  31. int lefts = 0;
  32. for(int i=center; i>=left;i--)
  33. {
  34. lefts += a[i];
  35. if(lefts>s1)
  36. {
  37. s1=lefts;
  38. }
  39. }
  40. int s2 = 0;
  41. int rights = 0;
  42. for(int i=center+1; i<=right;i++)
  43. {
  44. rights += a[i];
  45. if(rights>s2)
  46. {
  47. s2=rights;
  48. }
  49. }
  50. sum = s1+s2;
  51. if(sum<leftsum)
  52. {
  53. sum = leftsum;
  54. }
  55. if(sum<rightsum)
  56. {
  57. sum = rightsum;
  58. }
  59. }
  60. return sum;
  61. }
  62. int MaxSum(int n,int *a)
  63. {
  64. return MaxSubSum(a,0,n-1);
  65. }

算法所需的计算时间T(n)满足一下递归式：

解此递归方程可知：T(n)=O(nlogn)。

(3)动态规划算法求解

算法思路如下：

记，则所求的最大子段和为：

由b[j]的定义知，当b[j-1]>0时，b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得b[j]的动态规划递推式如下：

b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n。

具体代码如下：

  1. //3d4-1 最大子段和问题的动态规划算法
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSum(int n,int *a);
  6. int main()
  7. {
  8. int a[] = {-2,11,-4,13,-5,-2};
  9. for(int i=0; i<6; i++)
  10. {
  11. cout<<a[i]<<" ";
  12. }
  13. cout<<endl;
  14. cout<<"数组a的最大连续子段和为:"<<MaxSum(6,a)<<endl;
  15. return 0;
  16. }
  17. int MaxSum(int n,int *a)
  18. {
  19. int sum=0,b=0;
  20. for(int i=1; i<=n; i++)
  21. {
  22. if(b>0)
  23. {
  24. b+=a[i];
  25. }
  26. else
  27. {
  28. b=a[i];
  29. }
  30. if(b>sum)
  31. {
  32. sum = b;
  33. }
  34. }
  35. return sum;
  36. }

上述算法的时间复杂度和空间复杂度均为O(n)。

     2、最大子矩阵和问题
        (1)问题描述：给定一个m行n列的整数矩阵A，试求A的一个子矩阵，时期各元素之和为最大。

(2)问题分析：

用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵，其各元素之和记为：

最大子矩阵问题的最优值为。如果用直接枚举的方法解最大子矩阵和问题，需要O(m^2n^2)时间。注意到，式中，，设，则

容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MaxSum，可设计出最大子矩阵和动态规划算法如下:

  1. //3d4-5 最大子矩阵之和问题
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. const int M=4;
  6. const int N=3;
  7. int MaxSum(int n,int *a);
  8. int MaxSum2(int m,int n,int a[M][N]);
  9. int main()
  10. {
  11. int a[][N] = {{4,-2,9},{-1,3,8},{-6,7,6},{0,9,-5}};
  12. for(int i=0; i<M; i++)
  13. {
  14. for(int j=0; j<N; j++)
  15. {
  16. cout<<a[i][j]<<" ";
  17. }
  18. cout<<endl;
  19. }
  20. cout<<endl;
  21. cout<<"数组a的最大连续子段和为:"<<MaxSum2(M,N,a)<<endl;
  22. return 0;
  23. }
  24. int MaxSum2(int m,int n,int a[M][N])
  25. {
  26. int sum = 0;
  27. int *b = new int[n+1];
  28. for(int i=0; i<m; i++)//枚举行
  29. {
  30. for(int k=0; k<n;k++)
  31. {
  32. b[k]=0;
  33. }
  34. for(int j=i;j<m;j++)//枚举初始行i,结束行j
  35. {
  36. for(int k=0; k<n; k++)
  37. {
  38. b[k] += a[j][k];//b[k]为纵向列之和
  39. int max = MaxSum(n,b);
  40. if(max>sum)
  41. {
  42. sum = max;
  43. }
  44. }
  45. }
  46. }
  47. return sum;
  48. }
  49. int MaxSum(int n,int *a)
  50. {
  51. int sum=0,b=0;
  52. for(int i=1; i<=n; i++)
  53. {
  54. if(b>0)
  55. {
  56. b+=a[i];
  57. }
  58. else
  59. {
  60. b=a[i];
  61. }
  62. if(b>sum)
  63. {
  64. sum = b;
  65. }
  66. }
  67. return sum;
  68. }

以上代码MaxSum2方法的执行过程可用下图表示：


     3、最大m子段和问题

(1)问题描述：给定由n个整数(可能为负数)组成的序列a1,a2,a3……an,以及一个正整数m,要求确定此序列的m个不相交子段的总和达到最大。最大子段和问题是最大m字段和问题当m=1时的特殊情形。

(2)问题分析：设b(i,j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j](1<=i<=m,i<=j<=n),则所求的最优值显然为。与最大子段问题相似，计算b(i,j)的递归式为：

其中，表示第i个子段含a[j-1],而项表示第i个子段仅含a[j]。初始时，b(0,j)=0,(1<=j<=n);b(i,0)=0,(1<=i<=m)。

具体代码如下：

  1. //3d4-6 最大m子段问题
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSum(int m,int n,int *a);
  6. int main()
  7. {
  8. int a[] = {0,2,3,-7,6,4,-5};//数组脚标从1开始
  9. for(int i=1; i<=6; i++)
  10. {
  11. cout<<a[i]<<" ";
  12. }
  13. cout<<endl;
  14. cout<<"数组a的最大连续子段和为:"<<MaxSum(3,6,a)<<endl;
  15. }
  16. int MaxSum(int m,int n,int *a)
  17. {
  18. if(n<m || m<1)
  19. return 0;
  20. int **b = new int *[m+1];
  21. for(int i=0; i<=m; i++)
  22. {
  23. b[i] = new int[n+1];
  24. }
  25. for(int i=0; i<=m; i++)
  26. {
  27. b[i][0] = 0;
  28. }
  29. for(int j=1;j<=n; j++)
  30. {
  31. b[0][j] = 0;
  32. }
  33. //枚举子段数目，从1开始，迭代到m，递推出b[i][j]的值
  34. for(int i=1; i<=m; i++)
  35. {
  36. //n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形
  37. for(int j=i; j<=n-m+i; j++)
  38. {
  39. if(j>i)
  40. {
  41. b[i][j] = b[i][j-1] + a[j];//代表a[j]同a[j-1]一起，都在最后一子段中
  42. for(int k=i-1; k<j; k++)
  43. {
  44. if(b[i][j]<b[i-1][k]+a[j])
  45. b[i][j] = b[i-1][k]+a[j];//代表最后一子段仅包含a[j]
  46. }
  47. }
  48. else
  49. {
  50. b[i][j] = b[i-1][j-1]+a[j];//当i=j时，每一项为一子段
  51. }
  52. }
  53. }
  54. int sum = 0;
  55. for(int j=m; j<=n; j++)
  56. {
  57. if(sum<b[m][j])
  58. {
  59. sum = b[m][j];
  60. }
  61. }
  62. return sum;
  63. }

上述算法的时间复杂度为O(mn^2)，空间复杂度为O(mn)。其实，上述算法中，计算b[i][j]时，只用到了数组b的第i-1行和第i行的值。因而，算法中只要存储数组b的当前行，不必存储整个数组。另一方面，的值可以在计算i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。因此，算法可继续改进如下：

  1. //3d4-7 最大m子段问题
  2. #include "stdafx.h"
  3. #include <iostream>
  4. using namespace std;
  5. int MaxSum(int m,int n,int *a);
  6. int main()
  7. {
  8. int a[] = {0,2,3,-7,6,4,-5};//数组脚标从1开始
  9. for(int i=1; i<=6; i++)
  10. {
  11. cout<<a[i]<<" ";
  12. }
  13. cout<<endl;
  14. cout<<"数组a的最大连续子段和为:"<<MaxSum(3,6,a)<<endl;
  15. }
  16. int MaxSum(int m,int n,int *a)
  17. {
  18. if(n<m || m<1)
  19. return 0;
  20. int *b = new int[n+1];
  21. int *c = new int[n+1];
  22. b[0] = 0;//b数组记录第i行的最大i子段和
  23. c[1] = 0;//c数组记录第i-1行的最大i-1子段和
  24. for(int i=1; i<=m; i++)
  25. {
  26. b[i] = b[i-1] + a[i];
  27. c[i-1] = b[i];
  28. int max = b[i];
  29. //n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形
  30. for(int j=i+1; j<=i+n-m;j++)
  31. {
  32. b[j] = b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
  33. c[j-1] = max;//预先保存第j-1行的最大j-1子段和
  34. if(max<b[j])
  35. {
  36. max = b[j];
  37. }
  38. }
  39. c[i+n-m] = max;
  40. }
  41. int sum = 0;
  42. for(int j=m; j<=n; j++)
  43. {
  44. if(sum<b[j])
  45. {
  46. sum = b[j];
  47. }
  48. }
  49. return sum;
  50. }

上述算法时间复杂度为O(m(n-m))，空间复杂度为O(n)。当m或n-m为常数时，时间复杂度和空间复杂度均为O(n)。

最新文章

  1. SQL Server需要监控哪些计数器
  2. 快速掌握、学习HTML的方法
  3. java web学习总结(十五) -------------------JSP基础语法
  4. 做一个会PS切图的前端开发
  5. Spatial pyramid pooling (SPP)-net （空间金字塔池化）笔记（转）
  6. [题解]poj 1274 The Prefect Stall
  7. ROCK 聚类算法‏
  8. python学习（三）：matplotlib学习
  9. SQLAlchemy连接数据库并在django admin显示
  10. 把DataTable 转换成Json格式，适用于EasyUI 绑定DataGrid
  11. 一篇memcache基础教程
  12. unity3D 锁屏再开程序崩溃
  13. HDU--杭电--3790--最短路径问题
  14. Unity3d 实时折射和反射
  15. kettle于javascript步骤错误处理
  16. Java并发编程：同步锁、读写锁
  17. [SimplePlayer] 7. 多线程处理
  18. [UE4]引用Grabbable接口
  19. HTML经典模板总结（地址）
  20. DQN-深度Q网络

热门文章

  1. webview自总结
  2. spring 定时任务 scheduled Cron表达式
  3. [UE4]移除UI（User Widget）并销毁
  4. C# 生成日期维度值
  5. KafkaAPI实战
  6. oracle取出多个字段列中的最大值和最小值
  7. 搜狗输入法在Ubuntu下突然不能输入中文
  8. bool操作
  9. jvm 内存分配 （转）
  10. UiAutomatorHelper 调试类