题目标题

求一个矩阵中最大的二维矩阵(元素和最大).
如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码

参考解析
  1. #include <iostream>
  2. using namespace std;
  3. void GetMax2Matrix(int arr[][5], int row, int col, int result[][2])
  4. {
  5. int max_i = 0;
  6. int max_j = 0;
  7. int max_sum = -(1<<31);
  8. for(int i = 0; i < row-1; i++)
  9. for(int j = 0; j < col-1; j++)
  10. {
  11. int sum = arr[i][j] + arr[i+1][j] + arr[i][j+1] + arr[i+1][j+1];
  12. if(sum > max_sum)
  13. {
  14. max_sum = sum;
  15. max_i = i;
  16. max_j = j;
  17. }
  18. }
  19. result[0][0] = arr[max_i][max_j];
  20. result[0][1] = arr[max_i][max_j+1];
  21. result[1][0] = arr[max_i+1][max_j];
  22. result[1][1] = arr[max_i+1][max_j+1];
  23. }
  24. int main(void)
  25. {
  26. int arr[][5] = {1,2,0,3,4,
  27. 2,3,4,5,1,
  28. 1,1,5,3,0};
  29. int result[2][2];
  30. GetMax2Matrix(arr, 3, 5, result);
  31. for(int i = 0; i<2; i++)
  32. for(int j = 0; j < 2; j++)
  33. cout<<result[i][j]<<'\t';
  34. cout<<endl;
  35. return 0;
  36. }
  37. 时间复杂度:遍历矩阵(行迭代器为i,列迭代器为j),以当前遍历到的元素为首a[i,j],计算二维子矩阵的和(sum=a[i,j]+a[i+1,j]+a[i,j+1]+a[i+1,j+1]),并找出和最大的二维矩阵,注意矩阵的最后一行和最后一列不用遍历。时间复杂度为O(i*j)。