1、2维最大子段和

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #define MAX 1000
  6. int MaxSubInterval(int a[], int n)			//标准的一维最大子段和 
  7. {
  8. 	int sum = 0, tp = 0;
  9. 	for(int i=0; i<n; i++)
  10. 	{
  11. 		if(tp > 0)
  12. 			tp += a[i];
  13. 		else
  14. 			tp = a[i];
  15. 		if(sum < tp)
  16. 			sum = tp;
  17. 	}
  18. 	return sum;
  19. }
  21. int MaxSubMartix(int a[][MAX], int m, int n)		//二维最大子段和问题
  22. {
  23. 	int tp[MAX], sum = 0;
  24. 	for(int i=0; i<m; i++)
  25. 	{
  26. 		memset(tp, 0, sizeof(tp) );
  27. 		for(int j=i; j<m; j++)
  28. 		{
  29. 			for(int k=0; k<n; k++)
  30. 				tp[k] += a[j][k];		
  32. 			int max = MaxSubInterval(tp, n);
  33. 			if(max > sum)	sum = max;
  34. 		}
  35. 	}
  36. 	return sum;
  37. }
  39. /*
  41. int MaxSubInterval(int a[], int n, int size_y)			//一维的n个数的最大子段和 
  42. {
  43. 	int sum = 0, tp;
  44. 	for(int i=0; i<n-size_y; i++)
  45. 	{
  46. 		tp = 0;
  47. 		for(int j=i; j<i+size_y; j++)
  48. 		{
  49. 			if(tp > 0)
  50. 				tp += a[j];
  51. 			else
  52. 				tp = a[j];	
  53. 		}
  54. 		if(sum < tp)
  55. 				sum = tp;
  56. 	}
  57. 	return sum;
  58. }
  60. int MaxSubMartix(int a[][MAX], int m, int n, int size_x, int size_y)		//二维size_x * size_y 个数的最大子段和
  61. {
  62. 	int tp[MAX], sum = 0;
  63. 	for(int i=0; i<m-size_x; i++)
  64. 	{
  65. 		memset(tp, 0, sizeof(tp) );
  66. 		for(int j=i; j<i+size_x; j++)
  67. 		{
  68. 			for(int k=0; k<n; k++)
  69. 				tp[k] += a[j][k];		
  70. 		}
  71. 			int max = MaxSubInterval(tp, n, size_y);
  72. 			if(max > sum)	sum = max;
  73. 		
  74. 	}
  75. 	return sum;
  76. }
  77. */





附件列表

    【推广】 免费学中医，健康全家人
    原文地址：https://www.cnblogs.com/sober-reflection/p/61b4f77e8e98092b5ec2d10a54d04c9e.html