Register and join over 40,000 other developers!
Recent Topics

The Game You Are Waiting For?
WendellHarper  Dec 06 2020 01:21 PM

Quora and Reddit Backlinks
WendellHarper  Dec 06 2020 01:14 PM

Delete account
pindo  Jul 23 2020 01:33 AM

Print specific values from dictionary with a specific key name
Siten0308  Jun 20 2019 01:43 PM

Learn algorithms and programming concepts
johnnylo  Apr 23 2019 07:49 AM
Recent Blog Entries
Recent Status Updates
Popular Tags
 networking
 Managed C++
 stream
 console
 database
 authentication
 Visual Basic 4 / 5 / 6
 session
 Connection
 asp.net
 import
 syntax
 hardware
 html5
 array
 mysql
 java
 php
 c++
 string
 C#
 html
 loop
 timer
 jquery
 ajax
 javascript
 programming
 android
 css
 assembly
 c
 form
 vb.net
 xml
 linked list
 login
 encryption
 pseudocode
 calculator
 sql
 python
 setup
 help
 game
 combobox
 binary
 hello world
 grid
 innerHTML
8 replies to this topic
#1
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) :)
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) :)
#2
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.
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
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
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
#4
Posted 27 January 2012  03:00 AM
Thanks for your reply!
I've been looking at the pseudocode and I'm wondering if you're understanding me correctly or if I've misunderstood the code. Consider the following n x n array.
The red circle marks the largest subarray in the 2 dimensional array. Will the pseudocode return the value of the marked area?
Thanks
I've been looking at the pseudocode and I'm wondering if you're understanding me correctly or if I've misunderstood the code. Consider the following n x n array.
The red circle marks the largest subarray in the 2 dimensional array. Will the pseudocode return the value of the marked area?
Thanks
#5
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 clanguage 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
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 clanguage 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
#6
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' )
Thanks so much for the help
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' )
Thanks so much for the help
#7
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:
Try understanding it with a smaller array, 2x2
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 (zerobased)
This is my Java code for this. Dunno if my variables are better explaining than the obfuscated Ccode.
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 ^^
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 7The result is actually
9, 7, 3 5, 8, 2 0, 3, 5 5, 4, 3Which 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 56 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 (zerobased)
This is my Java code for this. Dunno if my variables are better explaining than the obfuscated Ccode.
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 ^^
#8
Posted 02 February 2012  12:47 PM
Thanks for clearing this up for me! I really appreciate it!
+rep (I hope my votingpower counts a little and isn't 0 )
+rep (I hope my votingpower counts a little and isn't 0 )
#9
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 submatrix (Given a MxN matrix of positive and negative integers, write code to find the submatrix 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
Also tagged with one or more of these keywords: array
Language Forums →
C# →
Counting the integers frequences in an array entered by the userStarted by AndreMarques, 27 Nov 2017 array, frequence 


Language Forums →
PHP →
How Come Variable Not Assigned And Php Knows Where To Look For Value ?Started by uniqueideaman, 06 May 2017 array 


Language Forums →
C and C++ →
help me . c++. ArraysStarted by girl2383, 06 Feb 2017 c++, array 


Language Forums →
C and C++ →
Selecting an element on a 2D arrayStarted by LonelyGuySylar, 18 May 2016 c, array, nested 


Language Forums →
Java →
Include a specific error, task, problem, or question in your titleStarted by rjb7, 15 Apr 2016 java, project, help, array, shift and 2 more... 

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