Problem

Farmer John has a rectangular grass pasture with N rows and M columns for the cows to graze on. Each pasture has a certain tastiness value. However, the gen alpha Bessie has gotten quite picky with what she eats.

Given a 2D array (template below) with skib NxM, please write functions for the following:

  1. getTotalGrass()
    • Return total sum of all “tastiness values” from the pastures in the 2D array
  2. maxSquare()
    • Because Bessie sometimes likes enjoying square grass patches, she wants to find the best one.
    • Returns the maximum sum of tastiness value of a square in the 2D array. (Square could be 1x1, 2x2, 3x3, etc.)
  3. maxSubarraySum()
    • Sometimes, Bessie enjoys eating grass in a line.
    • Return the maximum sum of a continuous subarray in this array if it was “flattened” to be a 1D array. In other words, make the 2D array into a 1D array by combining all rows and find the max subarray sum.

For an example case, see below in the code.

Extra Credit Opportunities

Extra Credit 1 (+0.01): What is the time complexity of your maxSquare code? Explain.

The skib complexity of maxSquare() is O(n^3) because i loop over all possible square sizes for each size thingymabob and iterate over all possible positions in the grid. For each square size there are O(n^2) possible positions and you do this for all the squar sizes. :yum:

Extra Credit 2 (+0.01): This is achieved if you get the optimal complexity for maxPatch.

skibbidi time complexity

Extra Credit 3 (+0.01): What is the time complexity of your maxSubarraySum code? Explain.

The skibbidi time complexity of maxSubarraySum() is O(n^4) cuz Flattening the array and calulating the prefix sum both take O(n * m) time but findin the maxum subarray sum requires two nested loops over the entire flattened array reslting in O(n^4) time complexity.

Extra Credit 4 (+0.01): This is achieved if you get the optimal complexity for maxSubarraySum.

2 pointers+prefix sum

public class GrassPasture {
    /** The 2D grid of pasture tastineess values */
    private int[][] pastures;

    /** Constructor initializes the field */
    public GrassPasture(int[][] pastures) {
        this.pastures = pastures;
    }

    /**
     * Returns sum of total tastiness for all values in 2D array
     */
    public int getTotalGrass() { 
        int TOTALgRaSs = 0;
        for (int i = 0; i < pastures.length; i++) {
            for (int j = 0; j < pastures[i].length; j++) {
                TOTALgRaSs += pastures[i][j];
            }
        }
        return TOTALgRaSs;
    }

    /**is 
     * Returns max sum of tastiness of a square in the 2D array (square can be 1x1, 2x2, etc.)
     */
    public int maxSquare() {
        int skibbidi=Integer.MIN_VALUE;int[][] skibsum=new int[pastures.length + 1][pastures[0].length + 1];int i= 1; // pissing you off because u made me do prefix sums and usaco AGAIN
        while (i<=pastures.length) {
            int j=1;
            while (j <= pastures[0].length) {
                skibsum[i][j]=pastures[i - 1][j - 1]+skibsum[i - 1][j]+skibsum[i][j - 1]-skibsum[i - 1][j - 1];
                j++;
            }
            i++;
        }
        int skib = 1;
        while (skib<=Math.min(pastures.length, pastures[0].length)) {
            i=0;
            while (i<=pastures.length-skib) {
                int j = 0;
                while (j<=pastures[0].length-skib) {
                    int sum=skibsum[i+skib][j+skib]-skibsum[i][j+skib]-skibsum[i+skib][j]+skibsum[i][j];
                    skibbidi=Math.max(skibbidi,sum);
                    j++;
                }
                i++;
            }
            skib++;
        }
        return skibbidi;
    }
    

    /**
     * Returns the maximum tastiness sum subarray in the flattened 2D grid
     */
    public int maxSubarraySum(){
        int idx=0;
        int[] Skibsigma=new int[pastures.length*pastures[0].length];
        for(int i=0;i<pastures.length;i++){
            for(int j=0;j<pastures[0].length;j++){
                Skibsigma[idx++]=pastures[i][j];
            }
        }
        int[] silentsigma=new int[Skibsigma.length+1];
        for(int i=1;i<=Skibsigma.length;i++){
            silentsigma[i]=silentsigma[i-1]+Skibsigma[i-1];
        }
        int maxSkibsigma=Integer.MIN_VALUE;
        for(int left=0;left<Skibsigma.length;left++){
            for(int right=left+1;right<=Skibsigma.length;right++){
                int sum=silentsigma[right]-silentsigma[left];
                maxSkibsigma=Math.max(maxSkibsigma,sum);
            }
        }
        return maxSkibsigma;
    }
    
}

int[][] pastures = {
    {-3, 6, -1}, // 2
    {2, -1, 5}, // 6
    {-9, 4, -1} // -6
};

GrassPasture gp = new GrassPasture(pastures);

System.out.println("Total Tastiness: " + gp.getTotalGrass());
// answer should be -2

System.out.println("Max Square Sum: " + gp.maxSquare());
// answer should be 9

System.out.println("Max Subarray Sum: " + gp.maxSubarraySum());
// answer should be 11


// If you are interested in the extra credit, you can answer below:


Total Tastiness: 2
Max Square Sum: 9
Max Subarray Sum: 11