Coding

Maximum sum of non adjacent elements

Asked at

Meta

Zeta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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)
    {

    }
}

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

At each index, either skip the current element and keep the best sum through the previous index, or take it and add it to the best sum through index i-2. Thus dp[i]=max(dp[i-1], nums[i]+dp[i-2]). Only the last two states are needed: initialize appropriately for the first element, then update current=max(prev1, value+prev2), followed by prev2=prev1 and prev1=current. This is O(n) time and O(1) space. With nonnegative values, skipping is always allowed; if a variant requires choosing at least one item or allows negatives, spell out the altered base case.

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

Hiring now

Zeta has 99 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer
New York, NY
Lead Software Engineer
Bangalore, India
Senior Software Engineer, Data Platform
San Francisco, CA

Or practice this question first

Next question