本文主要是介绍求最大和子矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题大家在很多地方都能找到。基本思路首先将矩阵二维问题转换为求一维数组的子数组问题。前面我们已经提到如何求一维数组的最大和子数组。我们可以写出每一列的全排列然后把每种排列都视为一个数组，然后输出最大的结果的矩阵就可以了。该实现我还没有验证。抽空将验证下。
void getMaxSumSubArray(int* list, int length, int& MaxSum,int& Maxstart, int& Maxend)
{
if( NULL == list || length < 1)
{
return;
}
int* result = new int[length];
int currentSum = 0;
int currentpos = 0;
for(int i = 0; i < length ; ++i)
{
// init and find the new begining of the max sum array
if(0 == currentpos && list[i] > 0)
{
Maxstart = i;
result[currentpos] = list[i];
currentSum = result[currentpos];
++currentpos;
}
else if(list[i] + currentSum > 0)
{
result[currentpos] = list[i];
currentSum = currentSum + list[i];
++currentpos;
}
else
{
currentSum = 0;
currentpos = 0;
}
if(currentSum > MaxSum)
{
MaxSum = currentSum;
Maxend = currentpos;
}
}
for(int i = 0; i < Maxend ; ++i)
{
printf("%d ", result[i]);
}
delete [] result;
}
void getMaxSumSubMatrix(int** list, int row, int column)
{
int * sumRow = new int [column];
int startRow = 0;
int endRow = 0;
int MaxSum = 0;
int Maxstart = 0;
int Maxend = 0;
for(int i = 0; i < column; ++i)
{
sumRow[i] = 0;
}
for(int i = 0; i < row; ++i)
{
for(int j= i; j < row; ++j)
{
for(int k = 0; k< column; ++k)
{
sumRow[k] += list[j][k];
}
int currentSum = 0;
int currentMaxstart = 0;
int currentMaxend = 0;
getMaxSumSubArray(sumRow, column, MaxSum, currentMaxstart, currentMaxend);
if(MaxSum < currentSum)
{
Maxstart = currentMaxstart;
Maxend = currentMaxend;
startRow = i;
endRow = j;
}
}
}
for(int i = startRow; i <= endRow; ++i)
{
for(int j = Maxstart; j <= Maxend; ++j)
{
printf("%d ", list[i][j]);
}
printf("\n");
}
delete [] sumRow ;
}
这篇关于求最大和子矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
