Round 5.

I swear some of the worst bugs are the ones where your logic makes perfect sense until someone finds a test case you somehow never thought of.

Here's today's one.

The problem

You are given an array of positive integers. You need to select some elements such that no two selected elements are adjacent.

Find the maximum possible sum.

For example, for [3, 2, 7, 10], choosing 3 and 10 gives a sum of 13.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    int ans = 0;

    for (int i = 0; i < n; ) {
        if (i + 1 < n && a[i + 1] > a[i]) {
            i += 2;
        } else {
            ans += a[i];
            i += 2;
        }
    }

    cout << ans << '\n';
}

The idea is basically to avoid taking an element when the next one is bigger, and otherwise take the current element.

Seems reasonable at first glance. If the next element is bigger, why bother taking the current one?

Except… maybe looking only one step ahead isn't enough.

Your mission

Find a counterexample that makes this code return the wrong answer.

• Keep the array as small as possible.
• Explain what the code prints and what the actual maximum sum is.
• Give a correct algorithm and explain why it works.

Bonus: can you solve this in O(n) using dynamic programming?

And please don't just throw a random huge array at it. I want the smallest counterexample that breaks the idea.

Let's see who gets it first.