Code Logo

Max Harvest with Rest

Published at05 Jan 2026
Created by
Hard 8 views
Like5

You are given a row of harvest fields, and each field has some value. If you harvest one field, you must rest on the next one, so two neighboring fields can never both be chosen.

That makes this a choice problem, not just a summing problem. A field with a big value might look tempting, but taking it can block another good option right beside it.

For example, with harvest = [1,2,3,1], the best total is 4 by taking the first and third fields. With harvest = [2,7,9,3,1], the best answer is 12, which comes from taking fields with values 2, 9, and 1. If the list is empty, the answer is 0.

So the task is to maximize the harvest total while always leaving at least one field of rest between chosen fields.

Example Input & Output

Example 1
Input
harvest = [2,7,9,3,1]
Output
12
Explanation

Harvest plots at indices 1, 3, and 4 (7+3+1) or indices 0,2,4 (2+9+1); the maximum is 12.

Example 2
Input
harvest = [1,2,3,1]
Output
4
Explanation

Harvest plots at indices 0 and 2 for a total of 4.

Example 3
Input
harvest = []
Output
0
Explanation

No plots mean no harvest.

Algorithm Flow

Recommendation Algorithm Flow for Max Harvest with Rest
Recommendation Algorithm Flow for Max Harvest with Rest

Solution Approach

This is the classic house robber dynamic programming pattern. At each field, you have two choices: skip it, or harvest it. If you harvest it, then the previous field must be skipped.

Let dp[i] be the best total we can get using fields up to index i. Then the transition is:

dp[i] = Math.max(dp[i - 1], harvest[i] + dp[i - 2])

The first option means we skip the current field and keep the best answer from before. The second option means we take the current field, so we add its value to the best answer from two fields earlier.

The base cases are simple:

dp[0] = harvest[0]

dp[1] = Math.max(harvest[0], harvest[1])

Once those are set, we fill forward until the end. The final DP value is the maximum harvest. This runs in O(n) time, and it can be optimized to O(1) extra space by keeping only the previous two values.

Best Answers

java
class Solution {
    public int max_harvest_with_rest(Object harvest) {
        if (harvest == null) return 0;
        int[] h = (int[]) harvest;
        if (h.length == 0) return 0;
        if (h.length == 1) return Math.max(0, h[0]);
        
        int prev2 = Math.max(0, h[0]);
        int prev1 = Math.max(prev2, h[1]);
        
        for (int i = 2; i < h.length; i++) {
            int current = Math.max(prev1, Math.max(0, h[i]) + prev2);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}