Maximum subsequence sum such that no three are consecutive

Problem Statement

Given an array of positive integers, find the maximum sum of a subsequence such that no three elements in the subsequence are consecutive in the original array.

Example:

• Input: arr = [1, 2, 3, 4, 5]
• Output: 12 (Pick elements 2, 3, 4, 5 → but not three consecutive; best is 1 + 2 + 4 + 5 = 12)

Noob-Friendly Explanation

Imagine you have a row of piggy banks, each with some coins. You want to collect as many coins as possible, but there's a rule: you can never pick three piggy banks in a row. You can pick two next to each other, but never three. So you need to be smart about which ones to skip to get the most coins.

Approach 1: Brute Force

Intuition

Generate all possible subsequences and check if any three elements in the subsequence are consecutive in the original array. Among all valid subsequences, find the one with the maximum sum.

Algorithm

1. Use recursion to decide for each element: include or exclude.
2. Track how many consecutive elements we've taken from the end.
3. If we've already taken two consecutive, we must skip the next one.

class Solution {
    public static int maxSumBrute(int[] arr, int index, int consecutiveCount) {
        if (index >= arr.length) return 0;

        // Exclude current element
        int exclude = maxSumBrute(arr, index + 1, 0);

        // Include current element (only if we haven't taken 2 consecutive already)
        int include = 0;
        if (consecutiveCount < 2) {
            include = arr[index] + maxSumBrute(arr, index + 1, consecutiveCount + 1);
        }

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(maxSumBrute(arr, 0, 0)); // Output: 12
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - at each index we branch into two choices
• Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

Use dynamic programming. Define dp[i] as the maximum sum we can get from the first i elements without picking three consecutive. At each position, we have three options: skip it, take it (and the previous was skipped), or take it along with the previous one (but the one before that was skipped).

Algorithm

1. Handle base cases: dp[0] = arr[0], dp[1] = arr[0] + arr[1], `dp[2] = max of picking any two out of the first three.
2. For i >= 3: dp[i] = max(dp[i-1], dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]).
3. Return dp[n-1].

class Solution {
    public static int maxSum(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        if (n == 1) return arr[0];
        if (n == 2) return arr[0] + arr[1];

        int[] dp = new int[n];
        dp[0] = arr[0];
        dp[1] = arr[0] + arr[1];
        dp[2] = Math.max(dp[1], Math.max(arr[0] + arr[2], arr[1] + arr[2]));

        for (int i = 3; i < n; i++) {
            // Option 1: skip arr[i], take best of first i-1
            // Option 2: take arr[i], skip arr[i-1], best of first i-2
            // Option 3: take arr[i] and arr[i-1], skip arr[i-2], best of first i-3
            dp[i] = Math.max(dp[i - 1],
                    Math.max(dp[i - 2] + arr[i],
                             dp[i - 3] + arr[i - 1] + arr[i]));
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(maxSum(arr)); // Output: 12
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(n) - the dp array of size n