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 size 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.

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

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

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

import java.util.Arrays;
public class GrassPasture {
    /** The 2D grid of pasture tastiness values */
    private int[][] pastures;

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

    public int getTotalGrass() {
        return Arrays.stream(pastures).flatMapToInt(Arrays::stream).sum();
    }

    public int maxSquare() {
        int height = pastures.length;
        int width = pastures[0].length;
        int[][] earlySum = new int[height + 1][width + 1];
        int maxSum = -9999;

        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                earlySum[i][j] = pastures[i - 1][j - 1] + earlySum[i - 1][j] + earlySum[i][j - 1] - earlySum[i - 1][j - 1];
            }
        }

        for (int size = 1; size <= Math.min(height, width); size++) {
            for (int i = size; i <= height; i++) {
                for (int j = size; j <= width; j++) {
                    int sum = earlySum[i][j] - earlySum[i - size][j] - earlySum[i][j - size] + earlySum[i - size][j - size];
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }

        return maxSum;
    }

    public int maxSubarraySum() {
        int[] flattened = new int[pastures.length * pastures[0].length];
        int index = 0;
        
        for (int[] row : pastures) {
            for (int val : row) {
                flattened[index++] = val;
            }
        }
        int maxSum = -9999;
        int currentSum = 0;
        for (int num : flattened) {
            currentSum = Math.max(num, currentSum + num);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }

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

    GrassPasture gp = new GrassPasture(pastures);
    System.out.println("Total Tastiness: " + gp.getTotalGrass()); // Expected: 2
    System.out.println("Max Square Sum: " + gp.maxSquare()); // Expected: 9
    System.out.println("Max Subarray Sum: " + gp.maxSubarraySum()); // Expected: 11

//EC

//Extra Credit 1 (+0.01): What is the time complexity of your maxSquare code? Explain.
//ngl idk if i had to guess it'd be O(NM) for the first part where its rows and columns and then O(min(NM) NM)
//for like O(NM)+O(min(NM)NM)
//where in the leetcode did u find this problem bro

//Extra Credit 2 (+0.01): This is achieved if you get the optimal complexity for maxPatch.
//not very sigma of thou :pensive:

//Extra Credit 3 (+0.01): What is the time complexity of your maxSubarraySum code? Explain.
//the time complexity of maxSubarraySum is O(NM) + O(N) with N being the number of rows and M being the columns
//it iterates through an NxM array before iterating through the 1d array


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

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