Katkat
Back

Maximize sum without choosing adjacent elements

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to solve optimization challenges using dynamic programming by identifying overlapping subproblems and optimal substructure in an array.

Problem Statement

You are given an array of non-negative integers nums. You want to collect the maximum possible sum of elements, with the constraint that you cannot pick two adjacent elements from the array. Write a function max_non_adjacent_sum(nums) that returns this maximum sum.

Examples

Example 1: Input: nums = [1, 2, 3, 1] Output: 4 Explanation: Pick elements 1 and 3 (indices 0 and 2). 1 + 3 = 4.

Example 2: Input: nums = [2, 7, 9, 3, 1] Output: 12 Explanation: Pick elements 2, 9, and 1 (indices 0, 2, 4). 2 + 9 + 1 = 12.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^4

Edge Cases

  • Empty array or single-element array.
  • Array with all zeros.
  • Array with only two elements.

Hints

Hint 1

For each element at index i, you have two choices: either include it (in which case you cannot include the element at i-1) or exclude it (in which case you can take the best sum up to i-1).

Hint 2

Define a recurrence relation where the max sum at index i is the maximum of (nums[i] + max_sum_up_to_i-2) and (max_sum_up_to_i-1).

Hint 3

You do not need to store the entire DP array; you only need to keep track of the results of the two most recent subproblems to achieve O(1) space complexity.

Follow-up questions

  • How would you modify your solution if the array was circular, meaning the first and last elements are now considered adjacent?
  • If you were asked to return the actual elements chosen to reach the maximum sum, how would you track the state changes?
  • What is the time and space complexity of your current solution, and can you prove it is optimal?