动态规划求最大字段和问题_动态规划法求最大子段和问题

  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.  

6. int MaxSum(int n,int *a,int& besti,int& bestj);

7.  

8. int main()

9. {

10. int a[] = {-2,11,-4,13,-5,-2};

11.  

12. for(int i=0; i<6; i++)

13. {

14. cout<<a[i]<<" ";

15. }

16.  

17. int besti,bestj;

18.  

19. cout<<endl;

20. cout<<"数组a的最大连续子段和为：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;

21.  

22. return 0;

23. }

24.  

25. int MaxSum(int n,int *a,int& besti,int& bestj)

26. {

27. int sum = 0;

28. for(int i=0; i<n; i++)//控制求和起始项

29. {

30. for(int j=i; j<n; j++)//控制求和结束项

31. {

32. int thissum = 0;

33. for(int k=i; k<=j; k++)//求和

34. {

35. thissum += a[k];

36. }

37.  

38. if(thissum>sum)//求最大子段和

39. {

40. sum = thissum;

41. besti = i;

42. bestj = j;

43. }

44. }

45. }

46. return sum;

47. }

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

 

1. //3d4-2 最大子段和问题的避免重复的简单算法

2. #include "stdafx.h"

3. #include <iostream>

4. using namespace std;

5.  

6. int MaxSum(int n,int *a,int& besti,int& bestj);

7.  

8. int main()

9. {

10. int a[] = {-2,11,-4,13,-5,-2};

11.  

12. for(int i=0; i<6; i++)

13. {

14. cout<<a[i]<<" ";

15. }

16.  

17. int besti,bestj;

18.  

19. cout<<endl;

20. cout<<"数组a的最大连续子段和为：a["<<besti<<":"<<bestj<<"]:"<<MaxSum(6,a,besti,bestj)<<endl;

21.  

22. return 0;

23. }

24.  

25. int MaxSum(int n,int *a,int& besti,int& bestj)

26. {

27. int sum = 0;

28. for(int i=0; i<n; i++)//控制求和起始项

29. {

30. int thissum = 0;

31. for(int j=i; j<=n; j++)//控制求和结束项

32. {

33. thissum += a[j];//求和

34. if(thissum>sum)

35. {

36. sum = thissum;

37. besti = i;

38. bestj = j;

39. }

40.  

41. }

42. }

43. return sum;

44. }

     (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.  

6. int MaxSubSum(int *a,int left,int right);

7. int MaxSum(int n,int *a);

8.  

9. int main()

10. {

11. int a[] = {-2,11,-4,13,-5,-2};

12.  

13. for(int i=0; i<6; i++)

14. {

15. cout<<a[i]<<" ";

16. }

17.  

18. cout<<endl;

19. cout<<"数组a的最大连续子段和为:"<<MaxSum(6,a)<<endl;

20.  

21. return 0;

22. }

23.  

24. int MaxSubSum(int *a,int left,int right)

25. {

26. int sum = 0;

27. if(left == right)

28. {

29. sum = a[left]>0?a[left]:0;

30. }

31. else

32. {

33. int center = (left+right)/2;

34. int leftsum = MaxSubSum(a,left,center);

35. int rightsum = MaxSubSum(a,center+1,right);

36.  

37. int s1 = 0;

38. int lefts = 0;

39. for(int i=center; i>=left;i--)

40. {

41. lefts += a[i];

42. if(lefts>s1)

43. {

44. s1=lefts;

45. }

46. }

47.  

48. int s2 = 0;

49. int rights = 0;

50. for(int i=center+1; i<=right;i++)

51. {

52. rights += a[i];

53. if(rights>s2)

54. {

55. s2=rights;

56. }

57. }

58. sum = s1+s2;

59. if(sum<leftsum)

60. {

61. sum = leftsum;

62. }

63. if(sum<rightsum)

64. {

65. sum = rightsum;

66. }

67.  

68. }

69. return sum;

70. }

71.  

72. int MaxSum(int n,int *a)

73. {

74. return MaxSubSum(a,0,n-1);

75. }

     算法所需的计算时间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.  

6. int MaxSum(int n,int *a);

7.  

8. int main()

9. {

10. int a[] = {-2,11,-4,13,-5,-2};

11.  

12. for(int i=0; i<6; i++)

13. {

14. cout<<a[i]<<" ";

15. }

16.  

17. cout<<endl;

18. cout<<"数组a的最大连续子段和为:"<<MaxSum(6,a)<<endl;

19.  

20. return 0;

21. }

22.  

23. int MaxSum(int n,int *a)

24. {

25. int sum=0,b=0;

26. for(int i=1; i<=n; i++)

27. {

28. if(b>0)//判断b的值为正或者是负，若是正继续加

29. {

30. b+=a[i];

31. }

32. else

33. {

34. b=a[i];

35. }

36. if(b>sum)

37. {

38. sum = b;

39. }

40. }

41. return sum;

42. }

     上述算法的时间复杂度和空间复杂度均为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.  

6. const int M=4;

7. const int N=3;

8.  

9. int MaxSum(int n,int *a);

10. int MaxSum2(int m,int n,int a[M][N]);

11.  

12. int main()

13. {

14. int a[][N] = {{4,-2,9},{-1,3,8},{-6,7,6},{0,9,-5}};

15.  

16. for(int i=0; i<M; i++)

17. {

18. for(int j=0; j<N; j++)

19. {

20. cout<<a[i][j]<<" ";

21. }

22. cout<<endl;

23. }

24.  

25. cout<<endl;

26. cout<<"数组a的最大连续子段和为:"<<MaxSum2(M,N,a)<<endl;

27.  

28. return 0;

29. }

30.  

31. int MaxSum2(int m,int n,int a[M][N])

32. {

33. int sum = 0;

34. int *b = new int[n+1];

35. for(int i=0; i<m; i++)//枚举行

36. {

37. for(int k=0; k<n;k++)

38. {

39. b[k]=0;//初始化为0 这个数组十分巧妙，可以解决求和问题

40. }

41.  

42. for(int j=i;j<m;j++)//枚举初始行i,结束行j

43. {

44. for(int k=0; k<n; k++)

45. {

46. b[k] += a[j][k];//b[k]为纵向列之和

47. int max = MaxSum(n,b);

48. if(max>sum)

49. {

50. sum = max;

51. }

52. }

53. }

54. }

55. return sum;

56. }

57.  

58. int MaxSum(int n,int *a)

59. {

60. int sum=0,b=0;

61. for(int i=1; i<=n; i++)

62. {

63. if(b>0)

64. {

65. b+=a[i];

66. }

67. else

68. {

69. b=a[i];

70. }

71. if(b>sum)

72. {

73. sum = b;

74. }

75. }

76. return sum;

77. }

     以上代码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.  

6. int MaxSum(int m,int n,int *a);

7.  

8. int main()

9. {

10. int a[] = {0,2,3,-7,6,4,-5};//数组脚标从1开始

11. for(int i=1; i<=6; i++)

12. {

13. cout<<a[i]<<" ";

14. }

15.  

16. cout<<endl;

17. cout<<"数组a的最大连续子段和为:"<<MaxSum(3,6,a)<<endl;

18. }

19.  

20. int MaxSum(int m,int n,int *a)

21. {

22. if(n<m || m<1)

23. return 0;

24. int **b = new int *[m+1];

25.  

26. for(int i=0; i<=m; i++)

27. {

28. b[i] = new int[n+1];

29. }

30.  

31. for(int i=0; i<=m; i++)

32. {

33. b[i][0] = 0;

34. }

35.  

36. for(int j=1;j<=n; j++)

37. {

38. b[0][j] = 0;

39. }

40.  

41. //枚举子段数目，从1开始，迭代到m，递推出b[i][j]的值

42. for(int i=1; i<=m; i++)

43. {

44. //n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形

45. for(int j=i; j<=n-m+i; j++)

46. {

47. if(j>i)

48. {

49. b[i][j] = b[i][j-1] + a[j];//代表a[j]同a[j-1]一起，都在最后一子段中

50. for(int k=i-1; k<j; k++)

51. {

52. if(b[i][j]<b[i-1][k]+a[j])

53. b[i][j] = b[i-1][k]+a[j];//代表最后一子段仅包含a[j]

54. }

55. }

56. else

57. {

58. b[i][j] = b[i-1][j-1]+a[j];//当i=j时，每一项为一子段

59. }

60. }

61. }

62. int sum = 0;

63. for(int j=m; j<=n; j++)

64. {

65. if(sum<b[m][j])

66. {

67. sum = b[m][j];

68. }

69. }

70. return sum;

71. }

72.  

     上述算法的时间复杂度为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.  

6. int MaxSum(int m,int n,int *a);

7.  

8. int main()

9. {

10. int a[] = {0,2,3,-7,6,4,-5};//数组脚标从1开始

11. for(int i=1; i<=6; i++)

12. {

13. cout<<a[i]<<" ";

14. }

15.  

16. cout<<endl;

17. cout<<"数组a的最大连续子段和为:"<<MaxSum(3,6,a)<<endl;

18. }

19.  

20. int MaxSum(int m,int n,int *a)

21. {

22. if(n<m || m<1)

23. return 0;

24. int *b = new int[n+1];

25. int *c = new int[n+1];

26.  

27. b[0] = 0;//b数组记录第i行的最大i子段和

28. c[1] = 0;//c数组记录第i-1行的最大i-1子段和

29.  

30. for(int i=1; i<=m; i++)

31. {

32. b[i] = b[i-1] + a[i];

33. c[i-1] = b[i];

34. int max = b[i];

35.  

36. //n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形

37. for(int j=i+1; j<=i+n-m;j++)

38. {

39. b[j] = b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];

40. c[j-1] = max;//预先保存第j-1行的最大j-1子段和

41.  

42. if(max<b[j])

43. {

44. max = b[j];

45. }

46. }

47. c[i+n-m] = max;

48. }

49.  

50. int sum = 0;

51. for(int j=m; j<=n; j++)

52. {

53. if(sum<b[j])

54. {

55. sum = b[j];

56. }

57. }

58. return sum;

59. }

60.  

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

--------------------- 本文来自 风仲达 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/liufeng_king/article/details/8632430?utm_source=copy