Frontend School

Maximize Non-Adjacent Harvest

DSA
easy

Maximize Non-Adjacent Harvest

Easy
Dynamic Programming
Arrays
1D DP

Overview

A farmer owns a long strip of land divided into several plots, each yielding a certain value of crops. To maintain soil health and prevent pest spread, the farmer has a strict rule: no two adjacent plots can be harvested in the same season. The farmer wants to maximize the total value of crops harvested under this constraint. This problem is critical for optimizing agricultural yield and making efficient resource allocation decisions.

What you need to do / Task

Your task is to implement a function maximizeNonAdjacentHarvest that calculates the maximum total value of crops the farmer can harvest from a given row of plots, adhering to the non-adjacent harvesting rule.

Input & output

  • Input: plotValues - An array of non-negative integers (number[] in TypeScript, array<number> in JavaScript), where plotValues[i] represents the monetary value of crops in the i-th plot.
  • Output: A single non-negative integer representing the maximum total value that can be harvested without selecting any two adjacent plots.

Clarifications

  • Empty field: If plotValues is an empty array, the maximum harvest value is 0.
  • Single plot: If plotValues contains only one plot, the maximum harvest value is the value of that single plot.
  • Non-negative values: All plot values are guaranteed to be non-negative (i.e., plotValues[i] >= 0).

Examples

1

Example 1

Input:

plotValues = [1, 2, 3, 1]

Output:

4

Note:

The maximum value is achieved by harvesting plots with values 1 and 3 (total 4). Picking 2 and 1 would yield 3, but 1 and 3 are better.

2

Example 2

Input:

plotValues = [2, 7, 9, 3, 1]

Output:

12

Note:

The maximum value is achieved by harvesting plots with values 2, 9, and 1 (total 12).

3

Example 3

Input:

plotValues = [0]

Output:

0

Note:

With only one plot of value 0, the maximum harvest is 0.

4

Example 4

Input:

plotValues = []

Output:

0

Note:

An empty field yields no harvest.

Constraints

Constraints & assumptions

  • 0 <= plotValues.length <= 10^5
  • 0 <= plotValues[i] <= 1000
  • The input array plotValues will only contain non-negative integers.

Out of scope

  • Input validation (you can assume plotValues will always be a valid array of non-negative numbers).
  • Handling extremely large harvest values that might overflow standard integer types (assume values fit within standard 32-bit or 64-bit integers).

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly identify and apply a dynamic programming approach to find the maximum non-adjacent sum?
  • Efficiency: Is the solution optimal in terms of time complexity (O(N)) and space complexity (O(1) after optimization)?
  • Edge Case Handling: Does the code gracefully handle edge cases such as empty arrays or arrays with a single element?
  • Code Quality: Is the code well-structured, readable, and easy to understand with appropriate variable names?

Loading editor...