Code Logo

Lantern Stall Picks

Published at05 Jan 2026
Created by
Array Manipulation Easy 13 views
Like2

Think of glowing lantern pieces that need to be handled in the right way. In Lantern Stall Picks, you are trying to work toward the right number by following one clear idea.

Maximize tokens from non-adjacent stalls A good way to think about it is to first understand what goes in, then what rule you must follow, and finally what shape the answer should have.

For example, if the input is tokens = [5,1,1,5], the answer is 10. Choose the first and last stalls to avoid adjacency and earn 10 tokens. Another example is tokens = [2,7,9,3,1], which gives 12. Select stalls worth 2, 9, and 1 tokens for a total of 12.

This is a friendly practice problem, but it still rewards careful reading. The key is understanding the rule clearly and then applying it carefully.

One helpful habit is to say the rule out loud in your own words before you start solving. If you can explain what counts, what changes, and what the final answer should look like, you are already much closer to the right solution.

Example Input & Output

Example 1
Input
tokens = [5,1,1,5]
Output
10
Explanation

Choose the first and last stalls to avoid adjacency and earn 10 tokens.

Example 2
Input
tokens = [2,7,9,3,1]
Output
12
Explanation

Select stalls worth 2, 9, and 1 tokens for a total of 12.

Example 3
Input
tokens = []
Output
0
Explanation

With no stalls, the total reward is zero.

Algorithm Flow

Recommendation Algorithm Flow for Lantern Stall Picks

Solution Approach

This problem is a classic example of maximizing a sum from non-adjacent elements, often called the "house robber" problem. The catch is that we cannot take two stalls next to each other, so a greedy approach (always taking the largest available) does not work. Instead, we need a small dynamic programming scan.

The key idea is to keep track of the best total we can achieve up to each position, using two running values: the best total ending at the previous stall and the best total ending two stalls back. For each new stall, we either skip it (keeping the previous best) or take it and add it to the best two positions earlier.

Here is the implementation:

function calculate_max_items(tokens) {
    let prev = 0, prev2 = 0;
    for (const token of tokens) {
        const current = Math.max(prev, prev2 + token);
        prev2 = prev;
        prev = current;
    }
    return prev;
}

We maintain two variables. prev holds the best total for the section we have processed so far, and prev2 holds the best total before that. For each token, we compute current as the larger of two choices: skip the current stall (use prev) or take it plus the best from two stalls back (prev2 + token). We then shift the values forward and repeat.

Let us trace tokens = [2, 7, 9, 3, 1]. Starting with prev = 0, prev2 = 0: for 2, current = max(0, 0 + 2) = 2. For 7, current = max(2, 0 + 7) = 7. For 9, current = max(7, 2 + 9) = 11. For 3, current = max(11, 7 + 3) = 11. For 1, current = max(11, 11 + 1) = 12. The final answer is 12, matching the expected output.

The greedy trap is clear here: taking 7 early looks good, but the optimal solution actually skips it to take 2, 9, 1. The DP comparison handles this automatically by evaluating both options at every step.

The time complexity is O(n) because we scan the array once, and the space complexity is O(1) since we only keep two running values.

Best Answers

java
class Solution {
    public int calculate_max_items(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int a = nums[0], b = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            int nb = Math.max(b, a + nums[i]);
            a = b; b = nb;
        }
        return b;
    }
}