Задачка на алгоритм

[an2ancan]

Помогите, пожалуйста, с задачей по программированию.

Задан массив $a$, состоящий из $n$ целых чисел. Введем функцию $S(i_1,\ldots,i_k)=a_{i_1}+\cdots+a_{i_k}$, принимающую последовательность индексов $i_1<\cdots<i_k (k\geq1;1\leq i_j \leq n$ $ \forall j:1\leq k)$и возвращающую сумму элементов массива в этих индексах. Требуется найти максимальное значение $S(i_1,…,i_k)$ при условии, что $i_1,\ldots,i_k$ — арифметическая прогрессия с положительным целочисленным шагом, то есть $i_{j+1} - i_j=d>0$ $\forall j:1 \leq j <k $

Мое решение было следующим:
1) заводим целочисленные переменные i,j;
2) для $i = 1 \ldots n/2:$
для $j = 1 \ldots i:$
проходим по массиву $a$ начиная с $a_j$ с шагом i и ищем макс сумму отрезка элементов массива (примерно по такому принципу http://www.geeksforgeeks.org/largest-su ... -subarray/, со стоимостью времени $O(n)$)

Ответом будет самая большая получившаяся сумма.

Получившееся решение имеет стоимость времени $O(n^2)$. Скажите, верна ли идея и есть ли решения со стоимостью времени меньшим чем $O(n^2)$. И если есть, помогите мне его найти. Если идея неверная, помогите мне в найти ошибку.

[iifat]

Думаю, всё верно. Только время $O(n^3)$ — линейный алгоритм внутри двойного цикла, да сам этот двойной цикл даёт квадратичный множитель. Арифметических прогрессий внутри отрезка как раз квадратичное количество, и каждую надо обработать, так что быстрее никак.

[kp9r4d]

Почему $i$ до $n/2$ а не до $n$?

[mihaild]

iifat в сообщении #1218117 писал(а):

Только время $O(n^3)$ — линейный алгоритм внутри двойного цикла, да сам этот двойной цикл даёт квадратичный множитель.

В цикле по $j$ мы каждый элемент перебираем всего один раз (в составе соответствующей арифметической прогрессии), так что сложность будет $O(n^2)$.

iifat в сообщении #1218117 писал(а):

Арифметических прогрессий внутри отрезка как раз квадратичное количество

А максимальных (которые нельзя продолжить) - линейное.

Ничего быстрее придумать сходу не получается (а доказывать нижние оценки на сложность - это всегда сложно).

[iifat]

kp9r4d в сообщении #1218120 писал(а):

Почему $i$ до $n/2$ а не до $n$?

Кстати, да.

mihaild в сообщении #1218136 писал(а):

В цикле по $j$ мы каждый элемент перебираем всего один раз (в составе соответствующей арифметической прогрессии), так что сложность будет $O(n^2)$

А вот тут не понял. Тело двойного цикла исполняется $O(n^2)$ раз, разве не?

-- 23.05.2017, 09:55 --

mihaild в сообщении #1218136 писал(а):

А максимальных (которые нельзя продолжить) - линейное

Может и так, подумать надо. Но если так, дело за малым — придумать эффективный, линейный же, алгоритм перебора.

-- 23.05.2017, 10:04 --

Не, подумал, всё равно не понял. Для шага $0\leq d\leq\lfloor\frac n2\rfloor$ можем начинать с любого не большего этого самого шага, как и сделано у ТС. Уже квадратичное количество.

-- 23.05.2017, 10:07 --

kp9r4d в сообщении #1218120 писал(а):

Почему $i$ до $n/2$ а не до $n$?

Это будут последовательности из двух элементов, не? Философский вопрос: $1, 100$ — это арифметическая прогрессия? А $100$?

[mihaild]

iifat в сообщении #1218144 писал(а):

Тело двойного цикла исполняется $O(n^2)$ раз, разве не?

На $i$-м шаге внешнего цикла мы делаем $i$ итераций внутреннего цикла. Каждая итерация занимает $O(\frac{n}{i})$ операций. Т.е. общее время на все итерации внутреннего цикла при данном $i$ - $O(\frac{n}{i} \cdot i) = O(n)$.

[iifat]

Действительно. Тут вы правы.

[an2ancan]

Цитата:

Почему $i$ до $n/2$ а не до $n$?

Просто после $n/2$ нет смысла увеличивать шаг. Ведь алгоритм следует от $j$ позиции до конца ( $j$ максимально $n/2$) c шагом $i$ (опять таки максимально $n/2$)

Почему я собственно задал этот вопрос, дело в том что я недавно решал эту задачу на тесте. При проверке были выявлены ошибки. Т.е. при определенном массиве ответ оказался неверным. С тех пор мне не дает покоя вопрос: где я ошибся.

[kp9r4d]

an2ancan
Ничего не понял из объяснения. Как у вас обработается случай $(1,-\infty,-\infty,-\infty,1)$ или какой-то такой подобный?

[an2ancan]

по условию n < 5000.
Вот код на С++:

#include <iostream>
#include <fstream>
#include <iostream>
using namespace std;
int maxSubArraySum(long a[], int size, int step)
{
    long maxSoFar = 0, maxEndingHere = 0;
    int stepCount;
    long maxSum = 0;

    for (stepCount = 0; stepCount < step; stepCount++)
    {
        for (int i = stepCount; i < size; i = i + step)
        {
            maxEndingHere = maxEndingHere + a[i];
            if (maxSoFar < maxEndingHere)
                maxSoFar = maxEndingHere;

            if (maxEndingHere < 0)
                maxEndingHere = 0;
        }
        maxSum = maxSum > maxSoFar ? maxSum:maxSoFar;
        maxSoFar = 0;
        maxEndingHere = 0;
    }
    return maxSum;
}
int main() {

    int n;
    ifstream fin("input.txt");
    fin >> n;

    long a[n];
    int counter;
    for (counter = 0; counter < n; counter ++)
    {
        fin >> a[counter];
    }

    fin.close();
    int step = 1;
    int maxSum = 0;


    while (step <= n/2)
    {
        long sum = maxSubArraySum(a, n, step);
        maxSum = (maxSum > sum ? maxSum:sum);
        step++;
    }

    ofstream fout("output.txt");
    fout << maxSum;
    fout.close();

    return 0;

}

input.txt - входной файл
В первой строке входных данных записано единственное число $n$ $( 1\leqn\leq5000)$ — количество элементов в массиве $a$.
Во второй строке входных данных записано $n$ целых чисел $a_1,\ldots,a_n$ $( -10^9 \leq a_i \leq 10^9)$ — элементы массива $a$, разделенные одним пробелом.

output.txt - ответ.

Думаю по коду будет яснее. Заранее прошу прощения за отсутствие коментариев

-- 23.05.2017, 11:37 --

вобщем да, действительно, шаг должен был быть до n. )))) Это я сглупил

[iifat]

an2ancan в сообщении #1218182 писал(а):

шаг должен был быть до n

Зависит от ответа на мой философский вопрос: называть ли последовательности из одного или двух чисел арифметическими. Ну вот представьте себе десять чисел. Какие могут быть арифметические прогрессии с шагом $6$? $1, 7; 2, 8; 3, 9; 4, 10; 5; 6; 7; 8; 9; 10$.

[an2ancan]

iifat в сообщении #1218195 писал(а):

an2ancan в сообщении #1218182 писал(а):

шаг должен был быть до n

Зависит от ответа на мой философский вопрос: называть ли последовательности из одного или двух чисел арифметическими. Ну вот представьте себе десять чисел. Какие могут быть арифметические прогрессии с шагом $6$? $1, 7; 2, 8; 3, 9; 4, 10; 5; 6; 7; 8; 9; 10$.

Боюсь что по условию этой задачи, да, нужно было назвать. Из вашего примера арифметические прогрессии с шагом $6$:
$(1;9)(7;4) (2;10)$ и т.д

[iifat]

an2ancan в сообщении #1218199 писал(а):

Боюсь что по условию этой задачи

Вам виднее.