Erst das Submatrix mit maximaler Summe?
https://stackoverflow.com/questions/2643908
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Input : Eine 2-dimensionales Array NxN - Matrix - mit positiven und negativen Elementen
Output : a. Untermatrix jeder Größe, so dass ihr Summe ist das Maximum unter allen möglichen Untermatrizen.
Voraussetzung : Komplexität Algorithmus zu sein von O (N ^ 3)
Geschichte: Mit Hilfe des Algorithmist, Larry und einer Modifikation des Kadane-Algorithmus, ist mir gelungen, das Problem lösen zum Teil , die die Summe nur ist die Bestimmung - unten Java.
Dank Ernesto , die den Rest des Problems zu lösen verwaltet, die die Grenzen der Matrix d oben links ist die Bestimmung, rechten unteren Ecken -. Unten in Ruby
Lösung
Über die tatsächliche Submatrix erholt, und nicht nur die maximale Summe, hier ist, was ich habe. Leider habe ich keine Zeit, meinen Code in Ihrer Java-Version zu übersetzen, so dass ich mit einigen Kommentaren in den wichtigsten Teilen meines Ruby-Code bin Entsendung
def max_contiguous_submatrix_n3(m)
rows = m.count
cols = rows ? m.first.count : 0
vps = Array.new(rows)
for i in 0..rows
vps[i] = Array.new(cols, 0)
end
for j in 0...cols
vps[0][j] = m[0][j]
for i in 1...rows
vps[i][j] = vps[i-1][j] + m[i][j]
end
end
max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right]
# these arrays are used over Kadane
sum = Array.new(cols) # obvious sum array used in Kadane
pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j
for i in 0...rows
for k in i...rows
# Kadane over all columns with the i..k rows
sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane
pos.fill(0)
local_max = 0 # we keep track of the position of the max value over each Kadane's execution
# notice that we do not keep track of the max value, but only its position
sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
for j in 1...cols
value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
if sum[j-1] > 0
sum[j] = sum[j-1] + value
pos[j] = pos[j-1]
else
sum[j] = value
pos[j] = j
end
if sum[j] > sum[local_max]
local_max = j
end
end
# Kadane ends here
# Here's the key thing
# If the max value obtained over the past Kadane's execution is larger than
# the current maximum, then update the max array with sum and bounds
if sum[local_max] > max[0]
# sum[local_max] is the new max value
# the corresponding submatrix goes from rows i..k.
# and from columns pos[local_max]..local_max
# the array below contains [max_sum,top,left,bottom,right]
max = [sum[local_max], i, pos[local_max], k, local_max]
end
end
end
return max # return the array with [max_sum,top,left,bottom,right]
end
Einige Hinweise zur Klarstellung:
verwende ich ein Array mit allen Werten speichern, um das Ergebnis der Einfachheit halber beziehen. Sie können nur fünf eigenständige Variablen verwenden: max, oben, links, unten, rechts. Es ist nur einfacher, in einer Linie mit dem Array zuweisen und dann das Unterprogramm kehrt das Array mit allen notwendigen Informationen.
Wenn Sie kopieren und fügen Sie diesen Code in einem Text-Highlight-fähigen Editor mit Ruby-Unterstützung werden Sie es offensichtlich besser verstehen. Hoffe, das hilft!
Andere Tipps
Hier ist eine Erklärung mit dem von ihm entsandten Code zu gehen. Es gibt zwei wichtige Tricks, diese Arbeit effizient zu machen: (I) Kadane Algorithmus und (II) unter Verwendung von Präfixsumme. Sie könnten auch zu (III) müssen die Tricks an die Matrix anzuwenden.
Teil I: Kadane Algorithmus
Kadane-Algorithmus ist ein Weg, um eine zusammenhängende Subsequenz mit maximaler Summe zu finden. Lassen Sie sich mit einem Brute-Force-Ansatz beginnen für die maximale zusammenhängende Subsequenz zu finden und dann halte es für die Optimierung Kadane-Algorithmus zu erhalten.
Angenommen, Sie die Sequenz haben:
-1, 2, 3, -2
Für den Brute-Force-Ansatz, zu Fuß entlang der Folge alle möglichen Teilsequenzen erzeugen, wie unten gezeigt. Unter Berücksichtigung aller Möglichkeiten, können wir beginnen, erweitern oder eine Liste mit jedem Schritt beenden.
At index 0, we consider appending the -1
-1, 2, 3, -2
^
Possible subsequences:
-1 [sum -1]
At index 1, we consider appending the 2
-1, 2, 3, -2
^
Possible subsequences:
-1 (end) [sum -1]
-1, 2 [sum 1]
2 [sum 2]
At index 2, we consider appending the 3
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum -1]
2 (end) [sum 2]
-1, 2, 3 [sum 4]
2, 3 [sum 5]
3 [sum 3]
At index 3, we consider appending the -2
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum 1]
2 (end) [sum 2]
-1, 2 3 (end) [sum 4]
2, 3 (end) [sum 5]
3, (end) [sum 3]
-1, 2, 3, -2 [sum 2]
2, 3, -2 [sum 3]
3, -2 [sum 1]
-2 [sum -2]
Für diesen Brute-Force-Ansatz, holen wir schließlich die Liste mit der besten Summe, (2, 3), und das ist die Antwort. Doch um diese effizienter zu machen, sollten Sie, dass Sie wirklich nicht jeder von den Listen halten müssen. Aus den Listen, die nicht beendet haben, müssen Sie nur das beste zu halten, können die anderen nicht besser machen. Aus den Listen, die beendet haben, können Sie brauchen nur die besten zu halten, und nur dann, wenn es besser ist, als diejenigen, die nicht beendet haben.
So können Sie verfolgen, was Sie brauchen, um mit nur einer Position Array und einem Summenarray. Das Positionsfeld wird wie folgt definiert: position[r] = s Spur der Liste hält, die an r und startet bei s endet. Und gibt sum[r] eine Summe für die Subsequenz bei index r endet. Dies wird optimiert Ansatz ist Kadane Algorithmus.
Beim Laufen durch das Beispiel wieder den Überblick über unsere Fortschritte zu halten auf diese Weise:
At index 0, we consider appending the -1
-1, 2, 3, -2
^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1
At index 1, we consider appending the 2
-1, 2, 3, -2
^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
At index 2, we consider appending the 3
-1, 2, 3, -2
^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
Again, we choose to extend because that gives a higher sum that starting a new one.
-1, 2, 3, -2
^
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
positions[3] = 3 sum[3] = 3
Auch hier ist die beste Summe ist 5 und die Liste ist aus dem Index 1 zum Index 2, die (2, 3).
Teil II: Präfixsumme
Wir wollen einen Weg, um die Summe entlang einer Reihe, für jeden Startpunkt zu jedem Endpunkt zu berechnen. Ich will diese Summe in O (1) Zeit zu berechnen, anstatt nur das Hinzufügen, die O (m) Zeit in Anspruch nimmt, wobei m die Anzahl der Elemente in der Summe ist. Mit etwas precomputing, kann dies erreicht werden. Hier ist wie. Angenommen, Sie haben eine Matrix:
a d g
b e h
c f i
Sie können diese Matrix precompute:
a d g
a+b d+e g+h
a+b+c d+e+f g+h+i
Sobald das geschieht Sie die Summe bekommen kann entlang einer beliebigen Spalte von jedem Start ausgeführt wird in der Spalte zum Endpunkt nur durch zwei Werte subtrahiert wird.
Teil III: Tricks zusammen Bringing the max finden Submatrix
Angenommen, Sie die obere und untere Reihe des max Submatrix kennen. Sie können dies tun:
- Ignoriere Zeilen über Ihre oberen Reihe und ignorieren Zeilen unter Ihrem Boden Zeile.
- Mit dem, was Matrix bleibt, sollten Sie die Verwendung Summe jeder Spalte bildet eine Sequenz (eine Art wie eine Reihe, die mehrere Zeilen darstellen). (Sie können jedes Element dieser Sequenz berechnen schnell mit dem Präfix Summen nähern.)
- Verwenden Sie Kadane Ansatz, um herauszufinden, am besten Teilfolge in dieser Reihenfolge. Die Indizes erhalten Sie wird Ihnen die links und rechts Positionen des besten Submatrix.
Nun, was herauszufinden eigentlich die Spitze und untere Reihe? Versuchen Sie einfach, alle Möglichkeiten. Versuchen Sie, die oben überall setzen Sie können und den Boden überall setzen können Sie, und führen Sie die Kadane-Basisverfahren für jede Möglichkeit zuvor beschrieben. Wenn Sie eine max finden, halten Sie den Überblick über die obere und untere Position.
Finden der Zeile und Spalte nimmt O (M ^ 2) wobei M die Anzahl der Zeilen ist. die Spalte zu finden, nimmt O (N) Zeit, in der N die Anzahl der Spalten ist. So Gesamtzeit ist O (m ^ 2 * N). Und wenn M = N ist die Zeit, ist O (N ^ 3).
Es gibt bereits viele Antworten, aber hier ist eine andere Java-Implementierung ich geschrieben habe. Es vergleicht drei Lösungen:
- Naive (Brute-Force) - O (n ^ 6) Zeit
- Die offensichtliche Lösung DP - O (n ^ 4) Zeit und O (n ^ 3) Raum
- Je clevere DP Lösung auf Basis von Kadane Algorithmus - O (n ^ 3) Zeit und O (n ^ 2) -Raum
Es sind Probenläufe für n = 10 bis n = 70 in Schritten von 10 mit einem schönen Ausgang Vergleichen der Laufzeit und Platzbedarf.
Code:
public class MaxSubarray2D {
static int LENGTH;
final static int MAX_VAL = 10;
public static void main(String[] args) {
for (int i = 10; i <= 70; i += 10) {
LENGTH = i;
int[][] a = new int[LENGTH][LENGTH];
for (int row = 0; row < LENGTH; row++) {
for (int col = 0; col < LENGTH; col++) {
a[row][col] = (int) (Math.random() * (MAX_VAL + 1));
if (Math.random() > 0.5D) {
a[row][col] = -a[row][col];
}
//System.out.printf("%4d", a[row][col]);
}
//System.out.println();
}
System.out.println("N = " + LENGTH);
System.out.println("-------");
long start, end;
start = System.currentTimeMillis();
naiveSolution(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms no auxiliary space requirements");
start = System.currentTimeMillis();
dynamicProgammingSolution(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for "
+ ((int) Math.pow(LENGTH, 4)) + " integers");
start = System.currentTimeMillis();
kadane2D(a);
end = System.currentTimeMillis();
System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " +
+ ((int) Math.pow(LENGTH, 2)) + " integers");
System.out.println();
System.out.println();
}
}
// O(N^2) !!!
public static void kadane2D(int[][] a) {
int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!)
for (int r = 0; r < LENGTH + 1; r++) {
for (int c = 0; c < LENGTH; c++) {
s[r][c] = 0;
}
}
for (int r = 1; r < LENGTH + 1; r++) {
for (int c = 0; c < LENGTH; c++) {
s[r][c] = s[r - 1][c] + a[r - 1][c];
}
}
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed!
for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed!
int[] s1 = new int[LENGTH];
for (int c = 0; c < LENGTH; c++) {
s1[c] = s[r2][c] - s[r1 - 1][c];
}
int max = 0;
int c1 = 0;
for (int c = 0; c < LENGTH; c++) {
max = s1[c] + max;
if (max <= 0) {
max = 0;
c1 = c + 1;
}
if (max > maxSum) {
maxSum = max;
maxRowStart = r1 - 1;
maxColStart = c1;
maxRowEnd = r2 - 1;
maxColEnd = c;
}
}
}
}
System.out.print("KADANE SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
// O(N^4) !!!
public static void dynamicProgammingSolution(int[][] a) {
int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width]
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 0; h < LENGTH + 1; h++) {
for (int w = 0; w < LENGTH + 1; w++) {
dynTable[r][c][h][w] = 0;
}
}
}
}
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 1; h <= LENGTH - r; h++) {
int rowTotal = 0;
for (int w = 1; w <= LENGTH - c; w++) {
rowTotal += a[r + h - 1][c + w - 1];
dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w];
}
}
}
}
for (int r = 0; r < LENGTH; r++) {
for (int c = 0; c < LENGTH; c++) {
for (int h = 0; h < LENGTH + 1; h++) {
for (int w = 0; w < LENGTH + 1; w++) {
if (dynTable[r][c][h][w] > maxSum) {
maxSum = dynTable[r][c][h][w];
maxRowStart = r;
maxColStart = c;
maxRowEnd = r + h - 1;
maxColEnd = c + w - 1;
}
}
}
}
}
System.out.print(" DP SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
// O(N^6) !!!
public static void naiveSolution(int[][] a) {
int maxSum = Integer.MIN_VALUE;
int maxRowStart = -1;
int maxColStart = -1;
int maxRowEnd = -1;
int maxColEnd = -1;
for (int rowStart = 0; rowStart < LENGTH; rowStart++) {
for (int colStart = 0; colStart < LENGTH; colStart++) {
for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) {
for (int colEnd = 0; colEnd < LENGTH; colEnd++) {
int sum = 0;
for (int row = rowStart; row <= rowEnd; row++) {
for (int col = colStart; col <= colEnd; col++) {
sum += a[row][col];
}
}
if (sum > maxSum) {
maxSum = sum;
maxRowStart = rowStart;
maxColStart = colStart;
maxRowEnd = rowEnd;
maxColEnd = colEnd;
}
}
}
}
}
System.out.print(" NAIVE SOLUTION | Max sum: " + maxSum);
System.out.print(" Start: (" + maxRowStart + ", " + maxColStart +
") End: (" + maxRowEnd + ", " + maxColEnd + ")");
}
}
Hier ist eine Java-Version von Ernesto Implementierung mit einigen Änderungen:
public int[][] findMaximumSubMatrix(int[][] matrix){
int dim = matrix.length;
//computing the vertical prefix sum for columns
int[][] ps = new int[dim][dim];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}
int maxSum = matrix[0][0];
int top = 0, left = 0, bottom = 0, right = 0;
//Auxiliary variables
int[] sum = new int[dim];
int[] pos = new int[dim];
int localMax;
for (int i = 0; i < dim; i++) {
for (int k = i; k < dim; k++) {
// Kadane over all columns with the i..k rows
reset(sum);
reset(pos);
localMax = 0;
//we keep track of the position of the max value over each Kadane's execution
// notice that we do not keep track of the max value, but only its position
sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
for (int j = 1; j < dim; j++) {
if (sum[j-1] > 0){
sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = pos[j-1];
}else{
sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
pos[j] = j;
}
if (sum[j] > sum[localMax]){
localMax = j;
}
}//Kadane ends here
if (sum[localMax] > maxSum){
/* sum[localMax] is the new max value
the corresponding submatrix goes from rows i..k.
and from columns pos[localMax]..localMax
*/
maxSum = sum[localMax];
top = i;
left = pos[localMax];
bottom = k;
right = localMax;
}
}
}
System.out.println("Max SubMatrix determinant = " + maxSum);
//composing the required matrix
int[][] output = new int[bottom - top + 1][right - left + 1];
for(int i = top, k = 0; i <= bottom; i++, k++){
for(int j = left, l = 0; j <= right ; j++, l++){
output[k][l] = matrix[i][j];
}
}
return output;
}
private void reset(int[] a) {
for (int index = 0; index < a.length; index++) {
a[index] = 0;
}
}
Mit Hilfe des Algorithmist und Larry und einer Modifikation des Kadane-Algorithmus, hier ist meine Lösung:
int dim = matrix.length;
//computing the vertical prefix sum for columns
int[][] ps = new int[dim][dim];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
if (j == 0) {
ps[j][i] = matrix[j][i];
} else {
ps[j][i] = matrix[j][i] + ps[j - 1][i];
}
}
}
int maxSoFar = 0;
int min , subMatrix;
//iterate over the possible combinations applying Kadane's Alg.
for (int i = 0; i < dim; i++) {
for (int j = i; j < dim; j++) {
min = 0;
subMatrix = 0;
for (int k = 0; k < dim; k++) {
if (i == 0) {
subMatrix += ps[j][k];
} else {
subMatrix += ps[j][k] - ps[i - 1 ][k];
}
if(subMatrix < min){
min = subMatrix;
}
if((subMatrix - min) > maxSoFar){
maxSoFar = subMatrix - min;
}
}
}
}
Das einzige, was links ist die Submatrix Elemente zu bestimmen, das heißt: die obere linke und die untere rechte Ecke des Submatrix. Jeder Vorschlag?
Das ist meine Implementierung von 2D Kadane Algorithmus. Ich denke, es ist klar. Das Konzept basiert auf nur Kadane Algorithmus. Die erste und zweite Schleife des Hauptteils (das in der Unterseite des Codes ist) ist jede Kombination der Zeilen zu holen und 3. Schleife wird durch jede folgende Spaltensumme 1D Kadane Algorithmus verwenden (das kann in const Zeit berechnet werden, weil (von combintation) Zeilen Aufheben der Vorverarbeitung der Matrix, die durch Werte von zwei subtrahieren). Hier ist der Code:
int [][] m = {
{1,-5,-5},
{1,3,-5},
{1,3,-5}
};
int N = m.length;
// summing columns to be able to count sum between two rows in some column in const time
for (int i=0; i<N; ++i)
m[0][i] = m[0][i];
for (int j=1; j<N; ++j)
for (int i=0; i<N; ++i)
m[j][i] = m[j][i] + m[j-1][i];
int total_max = 0, sum;
for (int i=0; i<N; ++i) {
for (int k=i; k<N; ++k) { //for each combination of rows
sum = 0;
for (int j=0; j<N; j++) { //kadane algorithm for every column
sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
total_max = Math.max(sum, total_max);
}
}
}
System.out.println(total_max);
Ich werde hier eine Antwort schreiben und kann tatsächlich c ++ Code hinzufügen, wenn es angefordert wird, weil ich vor kurzem durch diese gearbeitet hatte. Einige Gerüchte über eine Kluft und Eroberer, die dies in O (N ^ 2) lösen können, sind da draußen, aber ich habe keinen Code gesehen, dies zu unterstützen. Nach meiner Erfahrung ist die folgende, was ich gefunden habe.
O(i^3j^3) -- naive brute force method
o(i^2j^2) -- dynamic programming with memoization
O(i^2j) -- using max contiguous sub sequence for an array
if ( i == j )
O(n^6) -- naive
O(n^4) -- dynamic programming
O(n^3) -- max contiguous sub sequence
Hier finden Sie aktuelle JAMA Paket; Ich glaube, dass es Ihnen das Leben leichter machen.
Hier ist die C # Lösung. Ref: http://www.algorithmist.com/index.php/UVa_108
public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx)
{
MaxSumMatrix maxSumMtrx = new MaxSumMatrix();
// Step 1. Create SumMatrix - do the cumulative columnar summation
// S[i,j] = S[i-1,j]+ inMtrx[i-1,j];
int m = inMtrx.GetUpperBound(0) + 2;
int n = inMtrx.GetUpperBound(1)+1;
int[,] sumMatrix = new int[m, n];
for (int i = 1; i < m; i++)
{
for (int j = 0; j < n; j++)
{
sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j];
}
}
PrintMatrix(sumMatrix);
// Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij
for (int x = 0; x < n; x++)
{
for (int y = x; y < n; y++)
{
int[] r_ij = new int[n];
for (int k = 0; k < n; k++)
{
r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k];
}
// Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum =>
// capture Sum, colStartIdx, ColEndIdx.
// capture current x as rowTopIdx, y as rowBottomIdx.
MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij);
if (currMaxSum.maxSum > maxSumMtrx.sum)
{
maxSumMtrx.sum = currMaxSum.maxSum;
maxSumMtrx.colStart = currMaxSum.maxStartIdx;
maxSumMtrx.colEnd = currMaxSum.maxEndIdx;
maxSumMtrx.rowStart = x;
maxSumMtrx.rowEnd = y;
}
}
}
return maxSumMtrx;
}
public static void PrintMatrix(int[,] matrix)
{
int endRow = matrix.GetUpperBound(0);
int endCol = matrix.GetUpperBound(1);
PrintMatrix(matrix, 0, endRow, 0, endCol);
}
public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol)
{
StringBuilder sb = new StringBuilder();
for (int i = startRow; i <= endRow; i++)
{
sb.Append(Environment.NewLine);
for (int j = startCol; j <= endCol; j++)
{
sb.Append(string.Format("{0} ", matrix[i,j]));
}
}
Console.WriteLine(sb.ToString());
}
// Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum
public static MaxSum FindMaxSumSubarray(int[] inArr)
{
int currMax = 0;
int currStartIndex = 0;
// initialize maxSum to -infinity, maxStart and maxEnd idx to 0.
MaxSum mx = new MaxSum(int.MinValue, 0, 0);
// travers through the array
for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++)
{
// add element value to the current max.
currMax += inArr[currEndIndex];
// if current max is more that the last maxSum calculated, set the maxSum and its idx
if (currMax > mx.maxSum)
{
mx.maxSum = currMax;
mx.maxStartIdx = currStartIndex;
mx.maxEndIdx = currEndIndex;
}
if (currMax < 0) // if currMax is -ve, change it back to 0
{
currMax = 0;
currStartIndex = currEndIndex + 1;
}
}
return mx;
}
struct MaxSum
{
public int maxSum;
public int maxStartIdx;
public int maxEndIdx;
public MaxSum(int mxSum, int mxStart, int mxEnd)
{
this.maxSum = mxSum;
this.maxStartIdx = mxStart;
this.maxEndIdx = mxEnd;
}
}
class MaxSumMatrix
{
public int sum = int.MinValue;
public int rowStart = -1;
public int rowEnd = -1;
public int colStart = -1;
public int colEnd = -1;
}
Hier ist meine Lösung. Es ist O (n ^ 3) in der Zeit und O (n ^ 2) -Raum. https://gist.github.com/toliuweijing/6097144
// 0th O(n) on all candidate bottoms @B.
// 1th O(n) on candidate tops @T.
// 2th O(n) on finding the maximum @left/@right match.
int maxRect(vector<vector<int> >& mat) {
int n = mat.size();
vector<vector<int> >& colSum = mat;
for (int i = 1 ; i < n ; ++i)
for (int j = 0 ; j < n ; ++j)
colSum[i][j] += colSum[i-1][j];
int optrect = 0;
for (int b = 0 ; b < n ; ++b) {
for (int t = 0 ; t <= b ; ++t) {
int minLeft = 0;
int rowSum[n];
for (int i = 0 ; i < n ; ++i) {
int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i];
rowSum[i] = i == 0? col : col + rowSum[i-1];
optrect = max(optrect, rowSum[i] - minLeft);
minLeft = min(minLeft, rowSum[i]);
}
}
}
return optrect;
}
Ich würde nur die NxN Array analysieren die -ves entfernen, was bleibt, ist die höchste Summe einer Untermatrix.
Die Frage, die Sie nicht sagt, haben die ursprüngliche Matrix intakt oder dass die Reihenfolge wichtig zu verlassen.
