Это была слишком заманчивая проблема, чтобы оставить ее нетронутой :-)
Я нашел решение проблемы на C/C++ здесь, и в основном я перевел его на C#. Решение для int
: s, но должно быть довольно легко преобразовать его в числовой тип по вашему вкусу. Вы также можете каким-то образом вернуть результаты findMaxSum
, я оставлю это в качестве упражнения.
// Driver program to test 2D Kadane method
void Main()
{
int[,] M = {{ 1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{ 3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}};
findMaxSum(M);
}
// Implementation of Kadane's algorithm for 1D array. The function returns the
// maximum sum and stores starting and ending indexes of the maximum sum subarray
// at addresses pointed by start and finish pointers respectively.
int kadane(int[] arr, out int start, out int finish, int n)
{
// initialize sum, maxSum
int sum = 0;
int maxSum = Int32.MinValue;
// Just some initial value to check for all negative values case
start = -1;
finish = -1;
int local_start = 0;
for (int i = 0; i < n; ++i)
{
sum += arr[i];
if (sum < 0)
{
sum = 0;
local_start = i+1;
}
else if (sum > maxSum)
{
maxSum = sum;
start = local_start;
finish = i;
}
}
// There is at-least one non-negative number
if (finish != -1)
return maxSum;
// Special Case: When all numbers in arr[] are negative
maxSum = arr[0];
start = finish = 0;
// Find the maximum element in array
for (int i = 1; i < n; i++)
{
if (arr[i] > maxSum)
{
maxSum = arr[i];
start = finish = i;
}
}
return maxSum;
}
// The main function that finds maximum sum rectangle in M[][]
void findMaxSum(int[,] M)
{
int ROW = M.GetLength(0);
int COL = M.GetLength(1);
// Variables to store the final output
int maxSum = Int32.MinValue;
int finalLeft = -1, finalRight = -1, finalTop = -1, finalBottom = -1;
// Set the left column
for (int left = 0; left < COL; ++left)
{
// Initialize all elements of temp as 0
int start, finish;
int[] temp = new int[ROW];
// Set the right column for the left column set by outer loop
for (int right = left; right < COL; ++right)
{
// Calculate sum between current left and right for every row 'i'
for (int i = 0; i < ROW; ++i)
temp[i] += M[i, right];
// Find the maximum sum subarray in temp[]. The kadane() function
// also sets values of start and finish. So 'sum' is sum of
// rectangle between (start, left) and (finish, right) which is the
// maximum sum with boundary columns strictly as left and right.
int sum = kadane(temp, out start, out finish, ROW);
// Compare sum with maximum sum so far. If sum is more, then update
// maxSum and other output values
if (sum > maxSum)
{
maxSum = sum;
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
}
}
}
// Print final values
Console.WriteLine("(Top, Left) ({0},{1})", finalTop, finalLeft);
Console.WriteLine("(Bottom, Right) ({0},{1})", finalBottom, finalRight);
Console.WriteLine("Max sum is: {0}\n", maxSum);
}
person
Anders Gustafsson
schedule
21.11.2013