using System;
using System.Linq;
namespace test2
{
class Program
{
static void Main(string[] args)
{
int[][] int1 = new int[][] {
new int[] {1, 2, -1, -4, -20},
new int[] {-8, -3, 4, 2, 1},
new int[] {3, 8, 10, 1, 3},
new int[] {-4, -1, 1, 7, -6}
};
findMaxSubMatrix(int1);
//int[] kk = kadane(new int[] { -3,-2,-1 });
//foreach(var item in kk)
//{
// Console.WriteLine(item);
//}
Console.Read();
}
public static int[] kadane(int[] a)
{
//result[0] == maxSum, result[1] == start, result[2] == end;
int[] result = new int[] { int.MinValue, 0, -1 };
int currentSum = 0;
int localStart = 0;
for (int i = 0; i < a.Length; i++)
{
currentSum += a[i];
if (currentSum < 0)
{
currentSum = 0;
localStart = i + 1;
}
else if (currentSum > result[0])
{
result[0] = currentSum;
result[1] = localStart;
result[2] = i;
}
}
// all numbers in a are negative
if (result[2] == -1)
{
for (int i = 0; i < a.Length; i++)
{
if (a[i] > result[0])
{
result[0] = a[i];
result[1] = i;
result[2] = i;
}
}
}
return result;
}
/**
* To find and print maxSum, (left, top),(right, bottom)
*/
public static void findMaxSubMatrix(int[][] a)
{
int cols = a[0].Length;
int rows = a.Length;
int[] currentResult;
int maxSum = int.MinValue;
int left = 0;
int top = 0;
int right = 0;
int bottom = 0;
for (int leftCol = 0; leftCol < cols; leftCol++)
{
int[] tmp = new int[rows];
for (int rightCol = leftCol; rightCol < cols; rightCol++)
{
for (int i = 0; i < rows; i++)
{
tmp[i] += a[i][rightCol];
}
currentResult = kadane(tmp);
if (currentResult[0] > maxSum)
{
maxSum = currentResult[0];
left = leftCol;
top = currentResult[1];
right = rightCol;
bottom = currentResult[2];
}
}
}
Console.WriteLine("MaxSum: " + maxSum +
", range: [(" + left + ", " + top +
")(" + right + ", " + bottom + ")]");
}
}
}