/*
35.
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码
思想很简单，每次计算周围的四个矩阵的元素和
计算二维子矩阵的和(sum=a[i,j]+a[i+1,j]+a[i,j+1]+a[i+1,j+1]) 时间复杂度为O(i*j)
因为必须同时计算4个元素，有很多重复计算，所以可以适当减少点 复杂度相同 效率高些
*/
#include<iostream>
#include<stdio.h>
using namespace std;
int getMax2Array(int a[][5],int row,int col,int ans[])
{
int i,j,max,ans_i,ans_j,last2Sum,sum;
max=-1;
for(i=0;i<row-1;i++)
{
last2Sum=a[i][0]+a[i+1][0];//一行开始
for(j=1;j<col;j++)
{
sum=last2Sum;
last2Sum=a[i][j]+a[i+1][j];
sum+=last2Sum;
if(max<sum)
{
max=sum;
ans_i=i;//行是一样，列减1
ans_j=j-1;
}
}
}
ans[0]=ans_i;//返回最大位置
ans[1]=ans_j;
return max;
}
int main()
{
int a[3][5]={{1,2,0,3,4},{2,3,4,5,1},{1,1,5,3,0}};
int b[3][5]={{1,2,0,3,4},{2,3,4,5,1},{1,7,5,3,0}};
int ans[2],max,i;
max=getMax2Array(a,3,5,ans);
printf("原来数组中最大二维数组的和为：%d\n",max);
printf("%d %d\n",a[ans[0]][ans[1]],a[ans[0]][ans[1]+1]);
printf("%d %d\n",a[ans[0]+1][ans[1]],a[ans[0]+1][ans[1]+1]);
max=getMax2Array(b,3,5,ans);
printf("原来数组中最大二维数组的和为：%d\n",max);
printf("%d %d\n",b[ans[0]][ans[1]],b[ans[0]][ans[1]+1]);
printf("%d %d\n",b[ans[0]+1][ans[1]],b[ans[0]+1][ans[1]+1]);
return 0;
}