FastPrepFastPrep
Problem Brief

Max Harvested Crops

OA

Given a K * K matrix representing a field of crops, the goal is to collect as much crops as possible. Here are the rules for collecting crops:

  1. You can only move downward in a straight line in this field of crops. (Meaning from the top of the matrix to the bottom in a straight line).
  2. All crops within your path will get destroyed. And you can only collect crops to your left and right of your path. For example, you are at cell (1,1) in the matrix, you can then only collect crops at cell (1,0) and (1,2). You cannot collect the crop at (2,1), which is the cell below you since you can only collect crops left/right of your path.

Given the K * K matrix, return the maximum possible amount of crops that can be harvested based on the abovementioned rules of harvesting crops.

Input format:

K: the dimension of one side of the K * K matrix.
C: list of coordinates of crops (E.g. [(0,0), (1,2), (3,4)])

Output:

One integer representing maximum possible crops that can be harvested.

The inputs may not be 100% correct. For now, the two example images would be enough for you to understand the problem. I will modify the input nums once find more info. If you happen to know about them, feel free to contact Groot on discord server. TYSM in advance ^3~

1Example 1

Input
K = 3, C = [[0,1], [0,2], [1,0], [1,1], [2,0]]
Output
14
Explanation
Example 1 illustration
The "X" represents the path you took. In this case, we move downwards using the first and second column to collect the crops. The maximum crop harvested is 8+3+3 = 14 in this example. Note that the crop at (0,0) is destroyed since it was in your path. You can only harvested the crops at the sides (left/right) of your path.

2Example 2

Input
K = 3, C = [[0,2], [1,0], [1,1], [2,0], [2,1]]
Output
18
Explanation
Example 2 illustration
In this example, you are able to collect all crops without destroying any in your path. The optimal path is to move downwards on the second column all the way. And then later move down one step in the third column. Thus the answer is 1+3+3+8 = 18.

Constraints

Limits and guarantees your solution can rely on.

K <= 1 * 10^4
Number of crops <= 5 * 10^5
public int getMaxHarvestedCrops(int K, int[][] C) {
    // write your code here
}
Input

K

3

C

[[0,1], [0,2], [1,0], [1,1], [2,0]]

Output

14

Sign in to submit your solution.