Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Maximum sum of subarray (algorithm)

array

  • Please log in to reply
8 replies to this topic

#1 dkchokk

dkchokk

    CC Lurker

  • New Member
  • Pip
  • 7 posts

Posted 25 January 2012 - 10:25 AM

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) :-)
  • 0

#2 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 25 January 2012 - 11:13 AM

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.
  • 0

ti-99-sig.png
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
– Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid


#3 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts
  • Programming Language:C, C++, C#, JavaScript, PL/SQL, Delphi/Object Pascal, Visual Basic .NET, Pascal, Transact-SQL, Bash

Posted 25 January 2012 - 12:12 PM

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
  • 0

#4 dkchokk

dkchokk

    CC Lurker

  • New Member
  • Pip
  • 7 posts

Posted 27 January 2012 - 03:00 AM

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

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

Thanks :)
  • 0

#5 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 27 January 2012 - 07:17 AM

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
  • 0

#6 dkchokk

dkchokk

    CC Lurker

  • New Member
  • Pip
  • 7 posts

Posted 28 January 2012 - 02:47 AM

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 :)
  • 0

#7 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 31 January 2012 - 03:05 AM

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 ^^
  • -1

#8 dkchokk

dkchokk

    CC Lurker

  • New Member
  • Pip
  • 7 posts

Posted 02 February 2012 - 12:47 PM

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)
  • 0

#9 jones500

jones500

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 26 May 2013 - 01:44 AM

I know it is an old topic, but I'm writing here so I don't have to start a new one.

 

Anyway I have pretty much the same problem, I have to write the code in Python for Max sum sub-matrix (Given a MxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum).

I'm quite a beginner in programming and I don't understand Java, so it'll be very helpful if anyone could rewrtite it in Python or Pseudocode so I can code it in Python later.

 

Thanks a lot :)

 

 


  • 0





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download