Ok, so i really need help with this.
Basically, we are given a 2-dimensional array of integers (positive and negative and even zero), find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array.
We have been given the incomplete MaximumSum class. I need to implement the method, sum() which find the sub-rectangle with the largest sum and returns the sum. (I can create as many helper [private or public] methods and classes as needed).
The MaximumSum constructor has the following parameter:
ArrayList<ArrayList<Integer>> myArray;
And stores myArray as the 2-dimensional array of integers from which the sub-rectangle with the largest sum is to be found. The numbers in the array will be in the range [-127, 127].
What I'm having problems with is looping through each and EVERY elements of the 2D array in order to find the maximum Sum. I don't know if I am doing it right, because all of this looping is kind of hard to keep track.
This is what I have so far:
public class MaximumSum
{
ArrayList<ArrayList<Integer>> myArray;
private int sums[][];
public MaximumSum(ArrayList<ArrayList<Integer>> arr)
{
myArray = arr;
}
public int sum()
{
int size = myArray.size();
int max = 0;
int sum;
for(int i = 0; i < size; i++)
{
for(int x = 0; x < size; x ++)
{
sums[x] = myArray.get(x).get(i); // nullPointerException...help?!
}
}
for (int row = 0; row < size; row ++)
{
for (int col = 0; col < size; col ++)
{
sums[row + 1][col + 1] = sums [row][col + 1]
+ sums [row + 1][col]
- sums [row][col];
}
}
for (int startX = 1; startX <= size; startX ++)
{
for (int startY = 1; startY <= size; startY ++)
{
for (int endX = startX; endX <= size; endX ++)
{
for (int endY = startY; endY <= size; endY ++)
{
sum = sums[endX][endY]
- sums [startX - 1][endY]
- sums[endX][startY - 1]
+ sums [startX - 1][startY - 1];
if(sum > max)
{
max = sum;
}
}
}
}
}
return max;
}
So basically, I'm trying to loop over EVERY SINGLE element(s) of a 2D array. But I'm not really sure.
Can anyone look over the code and help me try to correct/improve it? And for some reason..one line of code gives me a nullPointerException..but I don't know why. Help please? :]