SubArraySum.java

SubArraySum.java

class SubArraySum {
        int[][] arr;
        int[][] sums;
        public SubArraySum(int[][] arr) {
                this.arr = arr;
                this.sums = new int[this.arr.length][this.arr[0].length];
                updateSums();
        }

        private void updateSums() {
                for(int row = 0; row < this.arr.length; row++) {
                        int sumLeft = 0;
                        for(int col = 0; col < this.arr[row].length; col++) {
                                int above = 0;
                                if(row > 0) above = this.sums[row-1][col];
                                this.sums[row][col] = this.arr[row][col] + above + sumLeft;
                                sumLeft += this.arr[row][col];
                        }
                }
        }

        public int findSum(int rowStart, int colStart, int height, int width) {
                int rowEnd = rowStart + height - 1;
                int colEnd = colStart + width - 1;
                return this.sums[rowEnd][colEnd]
                        // subtract the sum of everything above the start
                        - (rowStart == 0 ? 0 : this.sums[rowStart-1][colEnd])
                        
                        // subtract the sum of everything to the left of the start
                        - (colStart == 0 ? 0 : this.sums[rowEnd][colStart-1])

                        // add back part that was subtracted twice
                        + ( (rowStart == 0 || colStart == 0) ? 0 : this.sums[rowStart-1][colStart-1]);
        }
        public static void main(String[] args) {
                int rowStart = Integer.parseInt(args[0]);
                int colStart = Integer.parseInt(args[1]);
                int width = Integer.parseInt(args[2]);
                int height = Integer.parseInt(args[3]);

                int[][] testValues = {{1,2,3},{4,5,6},{7,8,9}};

                SubArraySum test = new SubArraySum(testValues);
                System.out.println("Values:");
                print2DArray(test.arr);
                System.out.println("Sums: ");
                print2DArray(test.sums);

                System.out.println("Finding the sum of the SubArray:");
                print2DArray(test.arr, rowStart, colStart, height, width);

                System.out.println("Sum: "+test.findSum(rowStart, colStart, width, height));
        }
        public static void print2DArray(int[][] arr, int... startValues) {
                int startRow = 0, startCol = 0;
                int height = arr.length, width = arr[0].length;
                if(startValues.length == 4) {
                        startRow = startValues[0];
                        startCol = startValues[1];
                        height = startValues[2];
                        width = startValues[3];
                }
                for(int i = startRow; i < startRow+height; i++) {
                        for(int j = startCol; j < startCol+width; j++) {
                                System.out.print(arr[i][j]+"\t");
                        }
                        System.out.println();
                }
        }
}