Задача 6868. Источник: Поляков. Задание КИМ 27
(Д. Козлов) Инспектор Лестрейд опять пытается перехитрить Шерлока Холмса, поэтому взял новое непростое дело. В огромном зале по кругу расставлено N ларцов (это значит, что первый и последний ларцы являются соседними), в каждом из которых лежит ровно одна карточка. На каждой карточке написано целое число от -1000 до 1000 включительно. Для того, чтобы приблизиться к разгадке этого дела, инспектору необходимо определить максимальную непрерывную сумму значений с карточек. Это значит, что рассматриваются карточки определённой непрерывной ненулевой группы ларцов (состоящей не меньше, чем из 1 ларца), например, если ларцов 10, то можно рассмотреть группу ларцов с номерами 3, 4, 5, 6, 7 или же, к примеру, все 10 ларцов. Однако нельзя рассматривать группу ларцов с номерами 1, 4, 5, 6, так как пропущены ларцы под номерами 2 и 3 (образовался разрыв). Помогите инспектору определить максимальную непрерывную сумму значений с карточек.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество ларцов. Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 1000 – число на каждой карточке.
Пример входного файла:
7
-2
4
-5
4
-5
9
4
При таких исходных данных инспектору Лестрейду удастся получить максимальную сумму, равную 15. Такое возможно при рассмотрении группы ларцов под номерами 6, 7, 1, 2. Ответ: 3. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Для решения данной задачи воспользуемся префиксными суммами. Чтобы обеспечить обработку по кругу, удвоим исходный массив. Таким образом, вторая половина массива/списка префиксных сумм будет давать движение по второму кругу. Самым простым решением является полный перебор пар префиксных сумм, но такое решение будет работать достаточно долго. На C++ перебор второго файла осуществляется несколько секунд, на PascalABC - около полутора минут, а на Python решение займет два-три часа даже на достаточно производительном компьютере.
Python
f = open("27-178a.txt")
n = int(f.readline())
a = [int(x) for x in f] * 2
p = [0]
for i in a:
p.append(p[-1] + i)
r = 0
for i in range(n + 1):
for j in range(i + 1, i + n + 1):
if p[j] - p[i] > r:
r = p[j] - p[i]
print(r)
PascalABC
var
n, r, i, j: Integer;
a: array [0..189932] of Integer;
p: array [0..379866] of Integer;
f: TEXT;
begin
Assign(f, '27-178b.txt');
Reset(f);
Readln(f, n);
for i := 0 to n - 1 do
Readln(f, a[i]);
p[0] := 0;
for i := 0 to n * 2 - 1 do
p[i + 1] := p[i] + a[i mod n];
r := 0;
for i := 0 to n do
for j := i + 1 to i + n do
if p[j] - p[i] > r then
r := p[j] - p[i];
Writeln(r);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-178b.txt");
int n;
f >> n;
int* a = new int[189933], * p = new int[379867];
for (int i = 0; i < n; i++)
f >> a[i];
p[0] = 0;
for (int i = 0; i < n * 2; i++)
p[i + 1] = p[i] + a[i % n];
int r = 0;
for (int i = 0; i <= n; i++)
for (int j = i + 1; j <= i + n; j++)
if (p[j] - p[i] > r)
r = p[j] - p[i];
cout << r << endl;
delete[] a;
delete[] p;
}
Более эффективное решение основано на понимании, что наибольшую сумму можно получить, если префиксная сумма конечного элемента будет как можно больше, а сумма предшествующая начальному элементу - как можно меньше. Для каждой вычитаемой суммы (предшествующей начальному элементу) найдем наибольшую в следующих n элементах. В большинстве случаев для поиска наибольшей суммы достаточно будет сравнить предыдущий максимум с последним элементом. Исключением является ситуация, когда позиция вычитаемой суммы дойдет до найденного максимального элемента. Тогда придется просмотреть следующие n элементов и найти среди них максимальный. Такое решение несколько сложнее, но быстро выдает результат на любом языке программирования.
Python
f = open("27-178b.txt")
n = int(f.readline())
a = [int(x) for x in f] * 2
p = [0]
for i in a:
p.append(p[-1] + i)
mx = max(p[:n + 1])
r = mx
for i in range(n + 1):
if p[i] == mx:
mx = max(p[i + 1:i + n + 1])
else:
mx = max(mx, p[i + n])
r = max(r, mx - p[i])
print(r)
PascalABC
var
n, r, max, i, j: Integer;
a: array [0..189932] of Integer;
p: array [0..379866] of Integer;
f: TEXT;
begin
Assign(f, '27-178b.txt');
Reset(f);
Readln(f, n);
for i := 0 to n - 1 do
Readln(f, a[i]);
p[0] := 0;
max := 0;
for i := 0 to n * 2 - 1 do
begin
p[i + 1] := p[i] + a[i mod n];
if (i <= n) and (p[i] > max) then
max := p[i];
end;
r := max;
for i := 0 to n do
begin
if p[i] = max then
begin
max := p[i + 1];
for j := i + 2 to i + n do
if p[j] > max then
max := p[j];
end;
if max - p[i] > r then
r := max - p[i];
end;
Writeln(r);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-178b.txt");
int n;
f >> n;
int *a = new int[189933], *p = new int[379867];
for (int i = 0; i < n; i++)
f >> a[i];
p[0] = 0;
int max = 0;
for (int i = 0; i < n * 2; i++)
{
p[i + 1] = p[i] + a[i % n];
if (i <= n && p[i] > max)
max = p[i];
}
int r = max;
for (int i = 0; i <= n; i++)
{
if (p[i] == max)
{
max = p[i + 1];
for (int j = i + 2; j <= i + n; j++)
if (p[j] > max)
max = p[j];
}
if (max - p[i] > r)
r = max - p[i];
}
cout << r << endl;
delete[] a;
delete[] p;
}
Ответ
2109 239600