1. Идея

Если бы дома стояли не по кругу, а в линию, задача была бы стандартной: для каждого дома решаем, брать его или не брать.

Но здесь есть важная особенность: первый и последний дома — соседи. Значит, их нельзя выбрать одновременно.

Из-за этого удобно разбить задачу на два случая:

• первый дом не рассматриваем, решаем задачу для домов с 1 по n - 1;
• последний дом не рассматриваем, решаем задачу для домов с 0 по n - 2.

В каждом из этих случаев дома уже стоят в линию, а не по кругу. Остаётся найти максимум для линейного массива и взять максимум из двух ответов.

2. Наблюдения

Наблюдение 1. Кольцо превращается в два отрезка

В оптимальном ответе:

• либо не выбран первый дом,
• либо не выбран последний дом.

Оба сразу могут быть не выбраны — это тоже допустимо, и такой вариант попадёт в один из этих двух случаев.

Поэтому достаточно посчитать:

• лучший ответ на отрезке 0..n-2,
• лучший ответ на отрезке 1..n-1.

И выбрать больший.

Наблюдение 2. Линейный вариант решается динамикой

Пусть дома идут подряд по прямой.

Для очередного дома i есть два варианта:

• не брать его, тогда ответ такой же, как для предыдущих домов;
• взять его, тогда дом i - 1 брать нельзя, значит прибавляем a[i] к ответу для позиции i - 2.

То есть переход такой:

dp[i] = max(dp[i - 1], dp[i - 2] + a[i])

Однако хранить весь массив dp не нужно. Достаточно двух последних значений:

• prev1 — ответ для предыдущей позиции,
• prev2 — ответ для позиции через одну назад.

3. Алгоритм

Случай n = 1

Если дом всего один, ответ равен a[0].

Функция для отрезка

Сделаем функцию solve_line(l, r), которая считает максимальную сумму на линейном отрезке домов от l до r.

Поддерживаем:

• prev2 = 0
• prev1 = 0

Далее для каждого i от l до r:

• cur = max(prev1, prev2 + a[i])
• prev2 = prev1
• prev1 = cur

После прохода prev1 и будет ответом.

Основное решение

Если n > 1, считаем:

• ans1 = solve_line(0, n - 2) — не берём последний дом;
• ans2 = solve_line(1, n - 1) — не берём первый дом.

Ответ:

• max(ans1, ans2)

4. Почему это работает

Докажем по шагам.

Почему достаточно двух случаев

Так как дома стоят по кругу, первый и последний — соседи. Значит, в допустимом наборе нельзя выбрать их одновременно.

Следовательно, любой допустимый ответ обязательно относится хотя бы к одному из двух типов:

• первый дом не выбран;
• последний дом не выбран.

Если первый дом не выбран, то задача сводится к линейной задаче на домах 1..n-1.

Если последний дом не выбран, то задача сводится к линейной задаче на домах 0..n-2.

Значит, оптимальный ответ по кругу равен максимуму из оптимальных ответов для этих двух линейных задач.

Почему правильно работает solve_line

Рассмотрим линейный отрезок.

Пусть после обработки некоторой позиции:

• prev1 хранит лучший ответ для уже просмотренных домов;
• prev2 хранит лучший ответ для домов без последнего из них.

Для нового дома i есть ровно два разумных выбора:

• не брать дом i, тогда лучший ответ равен prev1;
• взять дом i, тогда предыдущий дом брать нельзя, и сумма равна prev2 + a[i].

Лучший из этих вариантов:

cur = max(prev1, prev2 + a[i])

После этого сдвигаем значения, чтобы перейти к следующей позиции.

Таким образом, на каждом шаге поддерживается правильный оптимум, а после завершения прохода получаем правильный ответ для всего отрезка.

Почему итоговый максимум верен

Мы нашли оптимум:

• среди решений без последнего дома;
• среди решений без первого дома.

Любое допустимое решение по кругу входит хотя бы в один из этих двух наборов. Поэтому лучший из найденных двух ответов и есть глобальный оптимум.

5. Сложность

Функция solve_line работает за O(n) на своём отрезке.

Мы вызываем её два раза, поэтому общая сложность равна O(n).

Дополнительная память: O(1), не считая массива входных данных.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long solve_line(const vector<long long>& a, int l, int r) {
    long long prev2 = 0;
    long long prev1 = 0;
    for (int i = l; i <= r; i++) {
        long long cur = max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << a[0] << '\n';
        return 0;
    }

    long long ans1 = solve_line(a, 0, n - 2);
    long long ans2 = solve_line(a, 1, n - 1);

    cout << max(ans1, ans2) << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

def solve_line(l, r):
    prev2 = 0
    prev1 = 0
    for i in range(l, r + 1):
        cur = max(prev1, prev2 + a[i])
        prev2 = prev1
        prev1 = cur
    return prev1

if n == 1:
    print(a[0])
else:
    ans1 = solve_line(0, n - 2)
    ans2 = solve_line(1, n - 1)
    print(max(ans1, ans2))