7 replies to this topic

[dkchokk]

Hello all,

I'm a Computer Science student and I've just begun attending an algorithm course. I am by no means an experienced programmer. I was wondering if you could explain to me how to make a general algorithm to get the maximum sum of a subarray (2D) of an n x n array?

Thanks so much (in advance) :-)

[gregwarner]

There isn't really anything too complicated about this. You would want to use a nested loop structure: one loop inside another. The outer loop could iterate over the rows, for example, in your subarray, while your inner loop could iterate over the columns. This allows you to get access to each and every one of the elements in the subarray, provided you use the proper lower and upper bounds of this subarray as the constraints on your loops. From there, finding the sum is as simple as keeping a running total and adding the value of each element as you iterate through the loops.

[lespauled]

pseudo code:


MaxTotal = 0 <=== if all values are positive

foreach subarray in yourarray
{
currentTotal = 0

foreach item in subarray
{
currentTotal = currentTotal + item
}

if currentTotal > MaxTotal
MaxTotal = currentTotal
}

print maxtotal

[dkchokk]

Thanks for your reply!

I've been looking at the pseudo-code and I'm wondering if you're understanding me correctly or if I've misunderstood the code. Consider the following n x n array.

 9qgzz8.png   2.58K   6 downloads

The red circle marks the largest subarray in the 2 dimensional array. Will the pseudocode return the value of the marked area?

Thanks :)

[wim DC]

Google for "Kadane's algorithm"
Kadane's algorithm - Algowiki
The example there is for a 1D array obviously, but if you google you find Find Max sum in a 2D array | PROGRAMMING INTERVIEWS AND Maximum subarray sum problem - Algorithms

Both written in C, but try to understand the algorithm / the c-language and translate it into java and that should do the trick.


Edit: I tried this one: Find Max sum in a 2D array | PROGRAMMING INTERVIEWS
That one certainly works :P

[dkchokk]

I'm sorry but the algorithms I could find on the internet (including the ones you provided) are too difficult for me to understand. The variable names are often single character (making little sense) which confuses me - particularly because it's another language.

I'm still a rookie programmer so I've only really gotten used to Java's syntax.

I understand Kadane's 1D Algorithm perfectly. I need only know how to expand it to fit 2D arrays :-) (Heh 'only' :p)

Thanks so much for the help :)

[wim DC]

What the 2D algorithm REALLY does it, it simply sums up rows, so it becomes a 1D array, and then let the basic kadane algorithm run on that.
All "rows" checked like this:

Base array:
int[][] array = new int[][]
                {{ 9, 7,-3, 2},
                 { 5, 8, 2,-8},
                 { 0,-3, 5, 3},
                 {-5, 4, 3,-7}};


rows calculated:
9  7  -3  2  
14  15  -1  -6  
14  12  4  -3  
9  16  7  -10  


5  8  2  -8  
5  5  7  -5  
0  9  10  -12  


0  -3  5  3  
-5  1  8  -4  


-5  4  3  -7  

The result is actually

9, 7, -3
5, 8, 2
0, -3, 5
-5, 4, 3

Which sums up to 32 instead of the 29 of

9, 7
5, 8

Try understanding it with a smaller array, 2x2

int[][] array = new int[][]
                {{ 1, 4},
                 { 5, -5}};

rows checked:
1  4  
6  -1  

5  -5  

6 is the biggest subArray of all 3 1D arrays, 6 was made by summing up row 1 and 2, and taking only the first digit. eg X1=0, X2=0, Y1=0, Y2=1.
of the array 6, -1 kadane will come up with index 0 to 0 as biggest subArray. Those are X1, and X2. The Y values depend on how you made the 1D array. If it was by summing up row 2 and 4, then the y indexes would be 1 and 3 (zero-based)


This is my Java code for this. Dunno if my variables are better explaining than the obfuscated C-code.

public class Sample {
    private int x1, x2, max;


    public void calculate(){
        int max_sum = 0, finalX1 = 0, finalX2 = 0, finalY1 = 0, finalY2 = 0;
        int[][] array = new int[][]
                {{ 1, 4},
                 { 5, -5}};
        int[] tmp = new int[array[0].length];


        for (int y1 = 0; y1 < array.length; y1++) {              //y1 = starting row to start summing up
            for (int x = 0; x < array[y1].length; x++)
                tmp[x] = 0;


            for (int y2 = y1; y2< array.length; y2++) {          //y2 = next row to sum up.
                for (int x1 = 0; x1 < array[y1].length; x1++)
                    tmp[x1] += array[y2][x1];


                kadane(tmp);


                if (max > max_sum) {
                    finalY1 = y1;
                    finalY2 = y2;
                    finalX1 = x1;
                    finalX2 = x2;
                    max_sum = max;
                }
            }
        }


        System.out.println("max sum = " + max_sum);
        System.out.println("from: " + finalX1 + ", " + finalY1);
        System.out.println("to: " + finalX2 + ", " + finalY2);


        for(int i=finalX1 ; i<finalX2 ; i++){
            for(int j=finalY1 ; j<finalY2 ; j++){
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }


    private void kadane(int input[]) {
        int currentMax = 0;
        x1 = x2 = 0;
        int startIndex = 0;
        for (int i = 0; i < input.length; i++) {
            currentMax = currentMax + input[i];
            if (currentMax > max) {
                max = currentMax;
                x2 = i;
                x1 = startIndex;
            }
            if (currentMax < 0) {
                currentMax = 0;
                startIndex = i + 1;
            }
        }
    }


    public static void main(String[] args) {
        new Sample().calculate();
    }
}

Note: No idea why I said to translate it to Java last time. Guess I thought I was in the Java section on the forum and not in the "general programming" section ^^

[dkchokk]

Thanks for clearing this up for me! I really appreciate it!

+rep (I hope my voting-power counts a little and isn't 0 :p)