2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задачка на алгоритм
Сообщение22.05.2017, 23:52 


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

Задан массив $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)$. И если есть, помогите мне его найти. Если идея неверная, помогите мне в найти ошибку.

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 00:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 00:47 
Заслуженный участник
Аватара пользователя


09/02/14

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

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 01:53 
Заслуженный участник
Аватара пользователя


16/07/14
8335
Цюрих
iifat в сообщении #1218117 писал(а):
Только время $O(n^3)$ — линейный алгоритм внутри двойного цикла, да сам этот двойной цикл даёт квадратичный множитель.
В цикле по $j$ мы каждый элемент перебираем всего один раз (в составе соответствующей арифметической прогрессии), так что сложность будет $O(n^2)$.
iifat в сообщении #1218117 писал(а):
Арифметических прогрессий внутри отрезка как раз квадратичное количество
А максимальных (которые нельзя продолжить) - линейное.

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

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 02:53 
Заслуженный участник


16/02/13
4105
Владивосток
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$?

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 04:00 
Заслуженный участник
Аватара пользователя


16/07/14
8335
Цюрих
iifat в сообщении #1218144 писал(а):
Тело двойного цикла исполняется $O(n^2)$ раз, разве не?
На $i$-м шаге внешнего цикла мы делаем $i$ итераций внутреннего цикла. Каждая итерация занимает $O(\frac{n}{i})$ операций. Т.е. общее время на все итерации внутреннего цикла при данном $i$ - $O(\frac{n}{i} \cdot i) = O(n)$.

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 05:16 
Заслуженный участник


16/02/13
4105
Владивосток
Действительно. Тут вы правы.

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 10:30 


03/02/16
91
Цитата:
Почему $i$ до $n/2$ а не до $n$?

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

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

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 11:15 
Заслуженный участник
Аватара пользователя


09/02/14

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

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 11:25 


03/02/16
91
по условию 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. )))) Это я сглупил

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 12:02 
Заслуженный участник


16/02/13
4105
Владивосток
an2ancan в сообщении #1218182 писал(а):
шаг должен был быть до n
Зависит от ответа на мой философский вопрос: называть ли последовательности из одного или двух чисел арифметическими. Ну вот представьте себе десять чисел. Какие могут быть арифметические прогрессии с шагом $6$? $1, 7; 2, 8; 3, 9; 4, 10; 5; 6; 7; 8; 9; 10$.

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 12:12 


03/02/16
91
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)$ и т.д

 Профиль  
                  
 
 Re: Задачка на алгоритм
Сообщение23.05.2017, 12:44 
Заслуженный участник


16/02/13
4105
Владивосток
an2ancan в сообщении #1218199 писал(а):
Боюсь что по условию этой задачи
Вам виднее.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group