Max Harvested Crops
Learn this problem
Hudson River TradingOAProblem statement
You are given a K × K field. The sparse array C describes its crops: each entry [row, column, amount] means that the cell at that zero-based coordinate contains amount crops. Every coordinate not listed in C contains zero crops.
Choose a main column and an entry column. The entry column must be the main column or one of its immediate neighbors.
- In the first row, the path occupies every cell from the entry column through the main column, inclusive.
- In every remaining row, the path occupies the cell in the main column.
- Crops in path cells are destroyed.
- In each row, you harvest only the cells immediately to the left and right of that row's occupied path segment, when those cells are inside the field.
Return the maximum number of crops that can be harvested.
Complete getMaxHarvestedCrops, which receives int K and int[][] C and returns a long.
Function
getMaxHarvestedCrops(K: int, C: int[][]) → longExamples
Example 1
K = 3C = [[0,0,1], [0,2,3], [1,1,3], [1,2,3], [2,1,8]]return = 14Choose main column 0 and entry column 1. The path destroys cells (0,1), (0,0), (1,0), and (2,0). It harvests 3 crops at (0,2), 3 at (1,1), and 8 at (2,1), for a total of 14.
Example 2
K = 4C = [[0,3,3], [1,2,3], [2,0,1], [2,2,8], [3,2,3]]return = 18Choose main column 1 and entry column 2. The path harvests 3 crops at (0,3), 3 at (1,2), 1 + 8 in row 2, and 3 at (3,2), totaling 18.
Constraints
1 ≤ K ≤ 10^40 ≤ C.length ≤ 5 × 10^5- Every entry of
Chas the form[row, column, amount]. 0 ≤ row, column < K1 ≤ amount ≤ 10^9- Each coordinate appears at most once in
C. - The total crop amount fits in a signed
64-bitinteger.