Optimal Harvest — Problem Statement & Solution Guide
Problem Description
Given an integer array fruits of length n, you may collect fruits from any subset of trees provided that no two chosen trees are neighbours in the line. The goal is to maximize the total number of fruits collected. Return the largest possible sum.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Harvest"
WHY DOES IT MATTER?
The non‑adjacent selection pattern appears in budgeting, scheduling, and resource allocation where conflicts prohibit simultaneous choices; mastering it equips engineers to model constraints efficiently.
OPTIMIZATION CHALLENGE
Recognizing that the decision at index i depends only on the two previous optimal values collapses the state space from O(n) DP table to two scalars, turning a quadratic‑ish DP into a linear‑time, constant‑space algorithm.
REAL-WORLD CONNECTION
Think of a distributed backup system where two neighboring servers cannot be backed up at the same time due to network throttling – you must pick a subset of servers to maximize data saved without overloading adjacent links.
During the interview, write the recurrence first, then immediately suggest the two‑variable compression; it shows you understand both correctness and space‑efficiency.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic instance of the maximum‑sum‑non‑adjacent subsequence, often called the House Robber problem. A naive exhaustive search enumerates every subset of indices, leading to O(2^n) time because each element has two choices – take or skip – and the adjacency constraint forces a check for every combination, which quickly becomes infeasible for n>30. The optimal paradigm is dynamic programming: at each position i we decide whether to include fruits[i] (and then we must skip i‑1) or exclude it (and inherit the best result up to i‑1). This yields the recurrence dp[i] = max(dp[i‑1], dp[i‑2] + fruits[i]), where dp[i] stores the best sum considering the first i+1 trees. By building dp iteratively we collapse the exponential search space into a linear scan, guaranteeing optimality because each sub‑problem’s solution is reused for larger prefixes.
Interview Questions on This Problem
Q1How would you adapt the solution if you were allowed to pick at most two consecutive trees instead of zero?
Introduce a three‑state DP: dp[i][0] – skip i, dp[i][1] – pick i as the first of a possible pair, dp[i][2] – pick i as the second consecutive tree. Transition accordingly and take the max of the three at the end.
Q2What changes are needed if the fruit counts can be negative?
The same recurrence works, but you must initialize dp[0] = max(0, fruits[0]) and dp[1] = max(dp[0], fruits[1]) to avoid forcing a negative pick; effectively you may choose to collect nothing.
Q3Can you solve the problem in O(1) extra space? Explain how you would convey that in an interview.
Yes. Keep only two variables, prev1 and prev2, representing dp[i‑1] and dp[i‑2]. For each fruit, compute cur = max(prev1, prev2 + fruit), then shift prev2 = prev1, prev1 = cur. This yields the same result with constant memory.
Examples
Input
[3,2,5,10,7]
Output
15
Explanation: Select trees at indices 0, 2, and 4 (values 3, 5, 7). They are pairwise non‑adjacent and their sum 3+5+7=15 is greater than any other admissible selection.
Input
[4,1,1,4,2,1]
Output
9
Explanation: The optimal choice is indices 0, 3, and 5 (values 4, 4, 1). They satisfy the non‑adjacent condition and yield 4+4+1=9, which is the maximum achievable sum.
Input
[10]
Output
10
Explanation: With only one tree, the best (and only) selection is that tree itself, giving a total of 10.
Constraints
- 1 <= fruits.length <= 100000
- 0 <= fruits[i] <= 1000000000
- All calculations fit into 64‑bit signed integer
Optimal Approach & Strategy
Use dynamic programming with the recurrence dp[i]=max(dp[i-1],dp[i-2]+fruits[i]) and compress the DP array to two variables for O(n) time and O(1) space.
Brute Force Approach
Enumerate every subset of trees, discard those with adjacent selections, and track the maximum sum – exponential time.
Verified Code Solutions
/**
* @param {number[]} fruits
* @return {number}
*/
function optimalHarvest(fruits) {
const n = fruits.length;
if (n === 0) return 0;
if (n === 1) return fruits[0];
let include = fruits[0];
let exclude = 0;
for (let i = 1; i < n; i++) {
const newExclude = Math.max(include, exclude);
include = exclude + fruits[i];
exclude = newExclude;
}
return Math.max(include, exclude);
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const n = parseInt(lines[0]);
const fruits = lines[1].split(' ').map(Number);
console.log(optimalHarvest(fruits));
});#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int optimalHarvest(vector<int>& fruits) {
int n = fruits.size();
if (n == 0) return 0;
if (n == 1) return fruits[0];
int include = fruits[0];
int exclude = 0;
for (int i = 1; i < n; ++i) {
int newExclude = max(include, exclude);
include = exclude + fruits[i];
exclude = newExclude;
}
return max(include, exclude);
}
int main() {
int n;
cin >> n;
vector<int> fruits(n);
for (int i = 0; i < n; ++i) {
cin >> fruits[i];
}
cout << optimalHarvest(fruits) << endl;
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static int optimalHarvest(int[] fruits) {
int n = fruits.length;
if (n == 0) return 0;
if (n == 1) return fruits[0];
int include = fruits[0];
int exclude = 0;
for (int i = 1; i < n; i++) {
int newExclude = Math.max(include, exclude);
include = exclude + fruits[i];
exclude = newExclude;
}
return Math.max(include, exclude);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] fruits = new int[n];
String[] parts = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
fruits[i] = Integer.parseInt(parts[i]);
}
System.out.println(optimalHarvest(fruits));
}
}def optimalHarvest(fruits):
"""
Calculate the maximum sum of non-adjacent elements in the array.
Args:
fruits (list): A list of integers representing fruits on trees.
Returns:
int: The maximum possible sum of fruits collected.
"""
n = len(fruits)
if n == 0:
return 0
if n == 1:
return fruits[0]
include = fruits[0]
exclude = 0
for i in range(1, n):
new_exclude = max(include, exclude)
include = exclude + fruits[i]
exclude = new_exclude
return max(include, exclude)
if __name__ == "__main__":
n = int(input())
fruits = list(map(int, input().split()))
print(optimalHarvest(fruits))/**
* @param {number[]} fruits
* @return {number}
*/
function optimalHarvest(fruits) {
const n = fruits.length;
if (n === 0) return 0;
if (n === 1) return fruits[0];
let include = fruits[0];
let exclude = 0;
for (let i = 1; i < n; i++) {
const newExclude = Math.max(include, exclude);
include = exclude + fruits[i];
exclude = newExclude;
}
return Math.max(include, exclude);
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const n = parseInt(lines[0]);
const fruits = lines[1].split(' ').map(Number);
console.log(optimalHarvest(fruits));
});Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.