Maximum sum of non adjacent elements
Meta
ZetaThe problem
Given an integer array nums of size n. Return the maximum sum possible using the elements of nums such that no two elements taken are adjacent in nums.
Input: nums = [1, 2, 4] Output: 5 Explanation: [1, 2, 4], the underlined elements are taken to get the maximum sum.
Input: nums = [2, 1, 4, 9] Output: 11 Explanation: [2, 1, 4, 9], the underlined elements are taken to get the maximum sum.
Input: nums = [1, 7, 16, 8]
- n == nums.length
- 1 <= n <= 105
- 0 <= nums[i] <= 1000
cpp
class Solution {
public:
int nonAdjacent(vector<int>& nums) {
}
};java
class Solution {
public int nonAdjacent(int[] nums) {
}
}python
class Solution:
def nonAdjacent(self, nums):javascript
class Solution {
nonAdjacent(nums) {
}
}csharp
class Solution
{
public int NonAdjacent(int[] nums)
{
}
}go
func nonAdjacent(nums []int) int {
}Stuck? Show a way to structure it+
- 01Let `prev1` be the best sum through the previous index and `prev2` through two indices back.
- 02For each value, choose max of skipping it or taking it plus `prev2`.
- 03Shift the two state variables.
- 04Return the final best sum.
Reference answer
Then expect these follow-ups
How would you solve the circular-house variant?
Tests: case splitting
How would you reconstruct which indices were selected?
Tests: DP reconstruction
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question