Максимальная сумма подмассива по модулю М
Большинство из нас знакомы с проблемой подмассива максимальной суммы. Я наткнулся на вариант этой проблемы, который просит программиста вывести максимум всех сумм подмассива по модулю некоторого числа M.
Наивный подход к решению этого варианта состоял бы в том, чтобы найти все возможные суммы подмассивов (которые были бы порядка N^2, где N - размер массива). Конечно, этого недостаточно. Вопрос - как мы можем лучше?
Пример: рассмотрим следующий массив:
6 6 11 15 12 1
Пусть M = 13. В этом случае подмассив 6 6 (или 12 или 6 6 11 15 или 11 15 12) даст максимальную сумму ( = 12).
15 ответов
Мы можем сделать это следующим образом:
Поддержание массива sum который по индексу ith, содержит сумму модулей от 0 до ith,
Для каждого индекса ithнам нужно найти максимальную субсумму, которая заканчивается на этом индексе:
Для каждого подмассива (start + 1, i) мы знаем, что сумма мод этого подмассива
int a = (sum[i] - sum[start] + M) % M
Таким образом, мы можем получить только сумму, превышающую sum[i] если sum[start] больше чем sum[i] и как можно ближе к sum[i] насколько это возможно.
Это можно легко сделать, если вы используете двоичное дерево поиска.
Псевдокод:
int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
sum[i] = sum[i - 1] + A[i];
sum[i] %= M;
int a = tree.getMinimumValueLargerThan(sum[i]);
result = max((sum[i] - a + M) % M, result);
tree.add(sum[i]);
}
print result;
Временная сложность:O(n log n)
Пусть A будет нашим входным массивом с индексацией на основе нуля. Мы можем уменьшить A по модулю M без изменения результата.
Прежде всего, давайте уменьшим проблему до несколько более простой, вычислив массив P, представляющий суммы префиксов A, по модулю M:
A = 6 6 11 2 12 1
P = 6 12 10 12 11 12
Теперь давайте обработаем возможные левые границы наших массивов решений в порядке убывания. Это означает, что мы сначала определим оптимальное решение, которое начинается с индекса n - 1, затем то, которое начинается с индекса n - 2 и т. Д.
В нашем примере, если мы выбрали i = 3 в качестве нашей левой границы, возможные суммы подмассивов представлены суффиксом P[3..n-1] плюс константа a = A [i] - P [i]:
a = A[3] - P[3] = 2 - 12 = 3 (mod 13)
P + a = * * * 2 1 2
Глобальный максимум будет происходить и в одной точке. Поскольку мы можем вставить суффиксные значения справа налево, мы теперь сократили проблему до следующего:
Учитывая набор значений S и целых чисел x и M, найдите максимум S + x по модулю M
Это легко: просто используйте сбалансированное двоичное дерево поиска для управления элементами S. Учитывая запрос x, мы хотим найти наибольшее значение в S, которое меньше, чем M - x (это тот случай, когда при добавлении x не происходит переполнения). Если такого значения нет, просто используйте наибольшее значение S. И то, и другое можно сделать за O(log |S|).
Общее время выполнения этого решения: O(n log n)
Вот некоторый код C++ для вычисления максимальной суммы. Потребуются незначительные изменения, чтобы также вернуть границы оптимального подмассива:
#include <bits/stdc++.h>
using namespace std;
int max_mod_sum(const vector<int>& A, int M) {
vector<int> P(A.size());
for (int i = 0; i < A.size(); ++i)
P[i] = (A[i] + (i > 0 ? P[i-1] : 0)) % M;
set<int> S;
int res = 0;
for (int i = A.size() - 1; i >= 0; --i) {
S.insert(P[i]);
int a = (A[i] - P[i] + M) % M;
auto it = S.lower_bound(M - a);
if (it != begin(S))
res = max(res, *prev(it) + a);
res = max(res, (*prev(end(S)) + a) % M);
}
return res;
}
int main() {
// random testing to the rescue
for (int i = 0; i < 1000; ++i) {
int M = rand() % 1000 + 1, n = rand() % 1000 + 1;
vector<int> A(n);
for (int i = 0; i< n; ++i)
A[i] = rand() % M;
int should_be = 0;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j < n; ++j) {
sum = (sum + A[j]) % M;
should_be = max(should_be, sum);
}
}
assert(should_be == max_mod_sum(A, M));
}
}
Здесь уже перечислено множество отличных решений, но я хотел добавить одно, которое имеет время выполнения O(nlogn) без использования сбалансированного двоичного дерева, которого нет в стандартной библиотеке Python. Это решение не моя идея, но мне пришлось немного подумать, почему оно сработало. Вот код, объяснение ниже:
def maximumSum(a, m):
prefixSums = [(0, -1)]
for idx, el in enumerate(a):
prefixSums.append(((prefixSums[-1][0] + el) % m, idx))
prefixSums = sorted(prefixSums)
maxSeen = prefixSums[-1][0]
for (a, a_idx), (b, b_idx) in zip(prefixSums[:-1], prefixSums[1:]):
if a_idx > b_idx and b > a:
maxSeen = max((a-b) % m, maxSeen)
return maxSeen
Как и в других решениях, мы сначала вычисляем суммы префиксов, но на этот раз мы также отслеживаем индекс суммы префиксов. Затем мы сортируем суммы префиксов, так как мы хотим найти наименьшую разницу между суммами префиксов по модулю m - сортировка позволяет нам просто смотреть на соседние элементы, поскольку они имеют наименьшее различие.
На этом этапе вы можете подумать, что мы пренебрегаем важной частью проблемы - нам нужна наименьшая разница между суммами префиксов, но большая сумма префиксов должна стоять перед меньшей суммой префиксов (что означает, что у нее меньший индекс). В решениях, использующих деревья, мы обеспечиваем это, добавляя суммы префиксов одну за другой и пересчитывая лучшее решение.
Однако оказывается, что мы можем смотреть на соседние элементы и просто игнорировать те, которые не удовлетворяют нашему требованию индекса. Некоторое время это меня сбивало с толку, но главное понимание состоит в том, что оптимальное решение всегда будет исходить из двух смежных элементов . Докажу от противного. Предположим, что оптимальное решение получается из двух несмежных префиксных сумм x и z с индексами i и k, где z> x (отсортировано!) И k> i:
x ... z
k ... i
Рассмотрим одно из чисел между x и z и назовем его y с индексом j. Поскольку список отсортирован, x <y <z.
x ... y ... z
k ... j ... i
Префиксная сумма y должна иметь индекс j <i, иначе это было бы частью лучшего решения с z. Но если j <i, то j <k и y и x образуют лучшее решение, чем z и x! Таким образом, любые элементы между x и z должны образовывать лучшее решение с одним из двух, что противоречит нашему первоначальному предположению. Следовательно, оптимальное решение должно исходить из смежных сумм префиксов в отсортированном списке.
Из вашего вопроса кажется, что вы создали массив для хранения совокупных сумм (Prefix Sum Array) и вычисляете сумму подмассива arr[i:j] как (sum[j] - sum[i] + M) % M. (arr и sum обозначают данный массив и массив суммы префикса соответственно)
Вычисление суммы каждого подмассива приводит к O(n*n) алгоритм.
Возникает вопрос -
Неужели нам действительно нужно учитывать сумму каждого подмассива, чтобы достичь желаемого максимума?
Нет!
Для стоимости j Значение (sum[j] - sum[i] + M) % M будет максимальным, когда sum[i] просто больше, чем sum[j] или разница в том M - 1.
Это уменьшит алгоритм до O(nlogn).
Вы можете взглянуть на это объяснение! https://www.youtube.com/watch?v=u_ft5jCDZXk
Для меня все объяснения здесь были ужасны, так как я не получил часть поиска / сортировки. Как мы ищем / сортируем, было неясно.
Мы все знаем, что нам нужно строить prefixSum, имея в виду sum of all elems from 0 to i with modulo m
Я думаю, то, что мы ищем, понятно. Знаю это subarray[i][j] = (prefix[i] - prefix[j] + m) % m (с указанием суммы по модулю от индекса i до j), наши максимумы при заданном префиксе [i] всегда являются тем префиксом [j], который максимально приближен к префиксу [i], но немного больше.
Например, для m = 8, префикс [i] равен 5, мы ищем следующее значение после 5, которое находится в нашем prefixArray.
Для эффективного поиска (бинарный поиск) мы сортируем префиксы.
Что мы не можем сделать, так это сначала построить prefixSum, а затем выполнить итерацию снова от 0 до n и искать индекс в отсортированном массиве префиксов, потому что мы можем найти и endIndex, который меньше нашего startIndex, что не годится.
Поэтому мы выполняем итерацию от 0 до n, указывая endIndex нашей потенциальной максимальной суммы подмассива, а затем просматриваем наш отсортированный префиксный массив (который в начале пуст), который содержит отсортированные префиксы между 0 и endIndex.
def maximumSum(coll, m):
n = len(coll)
maxSum, prefixSum = 0, 0
sortedPrefixes = []
for endIndex in range(n):
prefixSum = (prefixSum + coll[endIndex]) % m
maxSum = max(maxSum, prefixSum)
startIndex = bisect.bisect_right(sortedPrefixes, prefixSum)
if startIndex < len(sortedPrefixes):
maxSum = max(maxSum, prefixSum - sortedPrefixes[startIndex] + m)
bisect.insort(sortedPrefixes, prefixSum)
return maxSum
Как вы можете прочитать в Википедии, существует решение, называемое алгоритмом Кадане, которое вычисляет максимальную сумму подмассива, наблюдая за максимальным окончанием подмассива в позиции i для всех позиций i, повторяя один раз по массиву. Тогда это решит проблему со сложностью O(n) во время выполнения.
К сожалению, я думаю, что алгоритм Кадане не может найти все возможные решения, когда существует более одного решения.
Реализация на Java, я не проверял это:
public int[] kadanesAlgorithm (int[] array) {
int start_old = 0;
int start = 0;
int end = 0;
int found_max = 0;
int max = array[0];
for(int i = 0; i<array.length; i++) {
max = Math.max(array[i], max + array[i]);
found_max = Math.max(found_max, max);
if(max < 0)
start = i+1;
else if(max == found_max) {
start_old=start;
end = i;
}
}
return Arrays.copyOfRange(array, start_old, end+1);
}
Вот код Java для максимальной суммы подмассива по модулю. Мы рассмотрим случай, когда мы не можем найти наименьший элемент в дереве, строго превышающий s[i]
public static long maxModulo(long[] a, final long k) {
long[] s = new long[a.length];
TreeSet<Long> tree = new TreeSet<>();
s[0] = a[0] % k;
tree.add(s[0]);
long result = s[0];
for (int i = 1; i < a.length; i++) {
s[i] = (s[i - 1] + a[i]) % k;
// find least element in the tree strictly greater than s[i]
Long v = tree.higher(s[i]);
if (v == null) {
// can't find v, then compare v and s[i]
result = Math.max(s[i], result);
} else {
result = Math.max((s[i] - v + k) % k, result);
}
tree.add(s[i]);
}
return result;
}
Несколько моментов с моей стороны, которые, надеюсь, помогут кому-то лучше понять проблему.
Вам не нужно добавлять
+Mк вычислению по модулю, как уже упоминалось,%оператор хорошо обрабатывает отрицательные числа, поэтомуa % M = (a + M) % MКак уже упоминалось, уловка состоит в том, чтобы построить таблицу сумм прокси так, чтобы
proxy[n] = (a[1] + ... a[n]) % M
Затем это позволяет представить maxSubarraySum[i, j] как
maxSubarraySum[i, j] = (proxy[j] - proxy[j]) % M
Уловка реализации состоит в том, чтобы построить прокси-таблицу по мере итерации по элементам, вместо того, чтобы сначала создавать ее, а затем использовать. Это потому, что для каждого нового элемента в массивеa[i] мы хотим вычислить proxy[i] и найти proxy[j] это больше, чем, но как можно ближе к proxy[i] (в идеале больше на 1 потому что это приводит к напоминанию о M - 1). Для этого нам нужно использовать продуманную структуру данных для построенияproxy таблица, сохраняя ее отсортированной и имея возможность быстро найти ближайший к proxy[i]. bisect.bisect_right - хороший выбор в Python.
См. Мою реализацию Python ниже (надеюсь, это поможет, но я знаю, что это не обязательно будет столь же кратким, как решения других):
def maximumSum(a, m):
prefix_sum = [a[0] % m]
prefix_sum_sorted = [a[0] % m]
current_max = prefix_sum_sorted[0]
for elem in a[1:]:
prefix_sum_next = (prefix_sum[-1] + elem) % m
prefix_sum.append(prefix_sum_next)
idx_closest_bigger = bisect.bisect_right(prefix_sum_sorted, prefix_sum_next)
if idx_closest_bigger >= len(prefix_sum_sorted):
current_max = max(current_max, prefix_sum_next)
bisect.insort_right(prefix_sum_sorted, prefix_sum_next)
continue
if prefix_sum_sorted[idx_closest_bigger] > prefix_sum_next:
current_max = max(current_max, (prefix_sum_next - prefix_sum_sorted[idx_closest_bigger]) % m)
bisect.insort_right(prefix_sum_sorted, prefix_sum_next)
return current_max
Полная реализация Java с O(n*log(n))
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.stream.Stream;
public class MaximizeSumMod {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Long times = Long.valueOf(in.readLine());
while(times --> 0){
long[] pair = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
long mod = pair[1];
long[] numbers = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
printMaxMod(numbers,mod);
}
}
private static void printMaxMod(long[] numbers, Long mod) {
Long maxSoFar = (numbers[numbers.length-1] + numbers[numbers.length-2])%mod;
maxSoFar = (maxSoFar > (numbers[0]%mod)) ? maxSoFar : numbers[0]%mod;
numbers[0] %=mod;
for (Long i = 1L; i < numbers.length; i++) {
long currentNumber = numbers[i.intValue()]%mod;
maxSoFar = maxSoFar > currentNumber ? maxSoFar : currentNumber;
numbers[i.intValue()] = (currentNumber + numbers[i.intValue()-1])%mod;
maxSoFar = maxSoFar > numbers[i.intValue()] ? maxSoFar : numbers[i.intValue()];
}
if(mod.equals(maxSoFar+1) || numbers.length == 2){
System.out.println(maxSoFar);
return;
}
long previousNumber = numbers[0];
TreeSet<Long> set = new TreeSet<>();
set.add(previousNumber);
for (Long i = 2L; i < numbers.length; i++) {
Long currentNumber = numbers[i.intValue()];
Long ceiling = set.ceiling(currentNumber);
if(ceiling == null){
set.add(numbers[i.intValue()-1]);
continue;
}
if(ceiling.equals(currentNumber)){
set.remove(ceiling);
Long greaterCeiling = set.ceiling(currentNumber);
if(greaterCeiling == null){
set.add(ceiling);
set.add(numbers[i.intValue()-1]);
continue;
}
set.add(ceiling);
ceiling = greaterCeiling;
}
Long newMax = (currentNumber - ceiling + mod);
maxSoFar = maxSoFar > newMax ? maxSoFar :newMax;
set.add(numbers[i.intValue()-1]);
}
System.out.println(maxSoFar);
}
}
Добавление кода STL C++11 на основе решения, предложенного @Pham Trung. Может быть удобно.
#include <iostream>
#include <set>
int main() {
int N;
std::cin>>N;
for (int nn=0;nn<N;nn++){
long long n,m;
std::set<long long> mSet;
long long maxVal = 0; //positive input values
long long sumVal = 0;
std::cin>>n>>m;
mSet.insert(m);
for (long long q=0;q<n;q++){
long long tmp;
std::cin>>tmp;
sumVal = (sumVal + tmp)%m;
auto itSub = mSet.upper_bound(sumVal);
maxVal = std::max(maxVal,(m + sumVal - *itSub)%m);
mSet.insert(sumVal);
}
std::cout<<maxVal<<"\n";
}
}
public static int MaxSequence(int[] arr)
{
int maxSum = 0;
int partialSum = 0;
int negative = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] < 0)
{
negative++;
}
}
if (negative == arr.Length)
{
return 0;
}
foreach (int item in arr)
{
partialSum += item;
maxSum = Math.Max(maxSum, partialSum);
if (partialSum < 0)
{
partialSum = 0;
}
}
return maxSum;
}
Я чувствую, что мои мысли совпадают с тем, что уже было опубликовано, но на всякий случай - решение Kotlin O(NlogN):
val seen = sortedSetOf(0L)
var prev = 0L
return max(a.map { x ->
val z = (prev + x) % m
prev = z
seen.add(z)
seen.higher(z)?.let{ y ->
(z - y + m) % m
} ?: z
})
Реализация на java с использованием treeset...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in)) ;
String[] str = read.readLine().trim().split(" ") ;
int n = Integer.parseInt(str[0]) ;
long m = Long.parseLong(str[1]) ;
str = read.readLine().trim().split(" ") ;
long[] arr = new long[n] ;
for(int i=0; i<n; i++) {
arr[i] = Long.parseLong(str[i]) ;
}
long maxCount = 0L ;
TreeSet<Long> tree = new TreeSet<>() ;
tree.add(0L) ;
long prefix = 0L ;
for(int i=0; i<n; i++) {
prefix = (prefix + arr[i]) % m ;
maxCount = Math.max(prefix, maxCount) ;
Long temp = tree.higher(prefix) ;
System.out.println(temp);
if(temp != null) {
maxCount = Math.max((prefix-temp+m)%m, maxCount) ;
}
//System.out.println(maxCount);
tree.add(prefix) ;
}
System.out.println(maxCount);
}
}
Вот одна реализация решения на java для этой проблемы, которая работает с использованием TreeSet в java для оптимизированного решения!
public static long maximumSum2(long[] arr, long n, long m)
{
long x = 0;
long prefix = 0;
long maxim = 0;
TreeSet<Long> S = new TreeSet<Long>();
S.add((long)0);
// Traversing the array.
for (int i = 0; i < n; i++)
{
// Finding prefix sum.
prefix = (prefix + arr[i]) % m;
// Finding maximum of prefix sum.
maxim = Math.max(maxim, prefix);
// Finding iterator poing to the first
// element that is not less than value
// "prefix + 1", i.e., greater than or
// equal to this value.
long it = S.higher(prefix)!=null?S.higher(prefix):0;
// boolean isFound = false;
// for (long j : S)
// {
// if (j >= prefix + 1)
// if(isFound == false) {
// it = j;
// isFound = true;
// }
// else {
// if(j < it) {
// it = j;
// }
// }
// }
if (it != 0)
{
maxim = Math.max(maxim, prefix - it + m);
}
// adding prefix in the set.
S.add(prefix);
}
return maxim;
}
Измените алгоритм Кадане, чтобы отслеживать #occurrence. Ниже приведен код.
#python3
#source: https://github.com/harishvc/challenges/blob/master/dp-largest-sum-sublist-modulo.py
#Time complexity: O(n)
#Space complexity: O(n)
def maxContiguousSum(a,K):
sum_so_far =0
max_sum = 0
count = {} #keep track of occurrence
for i in range(0,len(a)):
sum_so_far += a[i]
sum_so_far = sum_so_far%K
if sum_so_far > 0:
max_sum = max(max_sum,sum_so_far)
if sum_so_far in count.keys():
count[sum_so_far] += 1
else:
count[sum_so_far] = 1
else:
assert sum_so_far < 0 , "Logic error"
#IMPORTANT: reset sum_so_far
sum_so_far = 0
return max_sum,count[max_sum]
a = [6, 6, 11, 15, 12, 1]
K = 13
max_sum,count = maxContiguousSum(a,K)
print("input >>> %s max sum=%d #occurrence=%d" % (a,max_sum,count))