314. Maximum Subsequence Sum With No Three Consecutive Elements

Given an array of n non-negative integers, find the maximum possible sum of a subset of elements such that no three consecutive elements (by original array position) are all chosen.

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers, the array. Output: Print a single integer - the maximum subset sum with no three consecutive elements chosen.

1 <= n <= 10^4

Handling the first few indices explicitly as base cases (rather than trying to force the general recurrence to work for i=0,1,2) avoids referencing negative or undefined array indices - a clean, simple safeguard worth applying whenever a recurrence looks back more than one or two steps.

Find the maximum sum of a subset of elements such that no three consecutive array positions are all chosen. Brute force: Try every possible subset directly and check the no-three-consecutive constraint - this is exponential (2^n subsets), impractical for n up to 10^4. Optimised: Extending the 'no two adjacent' recurrence with a THIRD option (take two in a row, but never three) captures the exact constraint directly in the recurrence - each dp[i] still only depends on a small, fixed number of previous values (three instead of two), keeping the solution linear.

Build the answer left to right using the recurrence sum[i] = max(sum[i-1], sum[i-2] + arr[i], sum[i-3] + arr[i] + arr[i-1]), which says the best sum up to i either skips arr[i], takes only arr[i] together with the best sum ending two back, or takes arr[i] and arr[i-1] together with the best sum ending three back (taking three in a row is never allowed). Since each step only looks back three positions, keep just the last three running values instead of a full array. This gives a single linear pass with constant extra memory. Time: O(n) Space: O(1)

Notice the recursive state is fully described by just the current index and how many of the immediately preceding elements were taken (0, 1, or 2), so most of the exponential brute-force tree is recomputing identical subproblems. Cache the best achievable sum for each (index, consecutive-count) pair the first time it's computed and reuse it on repeat calls. This collapses the search to a small number of distinct states, each solved once. Time: O(n) Space: O(n)

Recursively decide, for each position, whether to include it or not, and track how many consecutive elements have been taken so far so you never let that streak reach three. Explore both branches (take/skip) for every index and take the best total sum found across all valid selections. This directly mirrors the problem definition, but because there are two choices at every one of the n positions, it explores an exponential number of subsets. Time: O(2^n) Space: O(n)

1. sum[i] = best achievable total considering only the first i+1 elements, ending the considered range at index i. 2. sum[i] = max(sum[i-1], sum[i-2]+arr[i], sum[i-3]+arr[i-1]+arr[i]) - either skip arr[i] entirely, include ONLY arr[i] (skipping arr[i-1]), or include BOTH arr[i-1] and arr[i] (skipping arr[i-2] to avoid three in a row). 3. Handle the first three indices as explicit base cases, since the recurrence references indices that may be negative for small i.

Time: O(n) - one single pass through the array. Space: O(1) if only the previous three sum values are kept, or O(n) if the full array is stored.

Test n = 1 and n = 2 (base cases with no valid three-in-a-row to avoid), an array of all zeros, and n at the upper bound of 10^4.

Be ready to connect this directly to 'Maximum Sum Such That No Two Elements Are Adjacent' - this is a natural, one-more-option extension of that exact same DP pattern.