Подтвердить что ты не робот

Максимальная сумма подмассивов по модулю M

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

Наивный подход к решению этого варианта состоял бы в том, чтобы найти все возможные субарейные суммы (которые были бы порядка N ^ 2, где N - размер массива). Конечно, это недостаточно. Вопрос в том, как мы можем сделать лучше?

Пример: рассмотрим следующий массив:

6 6 11 15 12 1

Пусть M = 13. В этом случае подрамка 6 6 (или 12 или 6 6 11 15 или 11 15 12) даст максимальную сумму (= 12).

4b9b3361

ОТВЕТЫ

Ответ 1

Мы можем сделать это следующим образом:

Поддержание массива sum, который при индексе ith содержит сумму модуля от 0 до ith.

Для каждого индекса ith нам нужно найти максимальную сумму, заканчивающуюся этим индексом:

Для каждого подмассива (начало + 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)

Ответ 2

Пусть A - наш входной массив с нулевым индексированием. Мы можем уменьшить A по модулю M без изменения результата.

Прежде всего, пусть проблема уменьшится немного легче, вычислив массив P, представляющий префиксные суммы A, по модулю M:

A = 6 6 11 2 12 1
P = 6 12 10 12 11 12

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

В нашем примере, если мы выбрали я = 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 (это тот случай, когда no переполнение происходит при добавлении x). Если такого значения нет, просто используйте наибольшее значение S. Оба могут быть выполнены в O (log | S |).

Общая продолжительность выполнения этого решения: O (n log n)

Здесь приведен код С++ для вычисления максимальной суммы. Это потребует незначительных адаптаций, чтобы также вернуть границы оптимального подмассива:

#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));
    }
}

Ответ 3

Вот код 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;
 }

Ответ 4

Общая реализация 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);

    }

}

Ответ 5

Добавление кода STL С++ 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";
    }
}

Ответ 6

Для меня все объяснения здесь были ужасны, так как я не получил часть поиска/сортировки. Как мы ищем/сортируем, было неясно.

Мы все знаем, что нам нужно построить prefixSum, то есть sum of all elems from 0 to я with modulo m

Я думаю, то, что мы ищем, понятно. Зная, что subarray[i][j] = (prefix[i] - prefix[j] + m) % m (указывает на сумму по модулю от индекса я до 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

Ответ 7

Как вы можете прочитать в Википедии, существует решение, называемое алгоритмом Кадане, которое вычисляет максимальную сумму подмассива, наблюдая за максимальным окончанием подмассива в позиции я для всех позиций 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);
    }

Ответ 8

Измените алгоритм Кадане, чтобы отслеживать #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))