80. Maximum Sum Such That No Two Elements Are Adjacent

Given an array of n non-negative integers, find the maximum possible sum of a subset of elements such that no two chosen elements are adjacent in the array.

Input: Two lines: the first contains n, the second contains n space-separated non-negative integers. Output: Print a single integer - the maximum sum of a subset with no two adjacent elements chosen.

1 <= n <= 10^5

This exact recurrence pattern (max of skip-vs-take-with-a-gap) generalizes directly to 'House Robber II' (a circular arrangement) and to the 'no THREE consecutive' variant seen elsewhere in this category - recognizing the base pattern makes these variants feel like natural extensions.

Find the maximum sum of a subset of array elements where no two chosen elements are adjacent. Brute force: Try every possible subset directly and check the no-two-adjacent constraint, taking the maximum sum - this is exponential (2^n subsets), impractical for n up to 10^5. Optimised: The recurrence directly encodes the ONLY two meaningful choices at each position (skip it, or take it and skip the one before) - since dp[i] only ever depends on the two immediately preceding values, this reduces an exponential subset search to a single O(n) linear pass with O(1) extra space.

The DP recurrence dp[i] = max(dp[i-1], dp[i-2] + arr[i]) only ever looks back two positions, so there is no need to store the entire table - just keep two running variables, 'incl' (best sum ending by including the previous element) and 'excl' (best sum ending by excluding it). At each step compute the new incl/excl pair from the old ones and slide forward, and the answer is max(incl, excl) at the end. This preserves the O(n) time of the DP approach while dropping memory usage to a constant handful of variables, which is optimal for this problem since every element must be examined at least once. Time: O(n) Space: O(1)

Notice the brute-force recursion only ever needs two pieces of information at index i: the best sum achievable considering elements 0..i if we include i, and if we exclude i. Define a recurrence dp[i] = max(dp[i-1], dp[i-2] + arr[i]) - either skip arr[i] and take the best answer up to i-1, or take arr[i] plus the best answer up to i-2 (since i-1 must then be excluded). Memoizing (or tabulating) this recurrence in an array turns the exponential brute force into a linear-time algorithm, since each subproblem is now solved exactly once. This is a huge improvement, though it still uses O(n) auxiliary memory for the DP table. Time: O(n) Space: O(n)

Try every possible subset of the array and check, for each one, whether it contains no two adjacent indices; among the valid subsets track the maximum sum. This can be done with recursion that, at each index, branches into two choices: skip the element, or take it and skip the next one. Every subset is examined independently with no reuse of earlier work, so the number of recursive calls grows exponentially with n. It is correct because it exhaustively covers every valid combination, but it is far too slow for n up to 10^5. Time: O(2^n) Space: O(n)

1. dp[i] = max(dp[i-1], dp[i-2] + arr[i]) - either SKIP this element (carrying forward dp[i-1]), or TAKE it (adding to dp[i-2], since the immediately previous element must then be skipped). 2. Only the two most recent dp values ever need to be kept in memory.

Time: O(n) - one single pass through the array. Space: O(1) - only the previous two dp values need to be kept in memory at any time.

Test n = 1 (answer is that single element), an array of all zeros, and n = 10^5 (upper bound) for the O(n) DP's performance.

This is a foundational DP pattern (often called 'House Robber') reused throughout many other problems - be ready to recognize it instantly and to explain the space optimization down to O(1) explicitly.