algorithm - Suma máxima de subarreglos módulo M

binary-search modulo

Question

La mayoría de nosotros estamos familiarizados con el problema de subarray de suma máxima . Me encontré con una variante de este problema que le pide al programador que genere el máximo de todas las sumas de subarreglos módulo algún número M.

El enfoque ingenuo para resolver esta variante sería encontrar todas las sumas de subarray posibles (que serían del orden de N ^ 2 donde N es el tamaño de la matriz). Por supuesto, esto no es lo suficientemente bueno. La pregunta es: ¿cómo podemos hacerlo mejor?

Ejemplo: Consideremos la siguiente matriz:

6 6 11 15 12 1

Sea M = 13. En este caso, el subarreglo 6 6 (o 12 o 6 6 11 15 o 11 15 12) producirá la suma máxima (= 12).

Answer 1

Agregar código STL C ++ 11 basado en la solución sugerida por @Pham Trung. Podría ser útil.

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

Answer 2

Aquí está el código de Java para el módulo de suma de sub array máximo. Manejamos el caso, no podemos encontrar el menor elemento en el árbol estrictamente mayor que 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;
 }

Answer 3

Dejemos que A sea ​​nuestra matriz de entrada con indexación basada en cero. Podemos reducir A módulo M sin cambiar el resultado.

En primer lugar, reduzcamos el problema a uno más sencillo calculando una matriz P que represente las sumas de prefijos de A , módulo M :

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

Ahora, procesemos los posibles bordes izquierdos de nuestros arreglos secundarios en orden decreciente. Esto significa que primero determinaremos la solución óptima que comienza en el índice n - 1 , luego la que comienza en el índice n - 2, etc.

En nuestro ejemplo, si elegimos i = 3 como nuestro borde izquierdo, las posibles sumas de subarreglo están representadas por el sufijo P [3..n-1] más una constante a = A [i] - P [i] :

a = A[3] - P[3] = 2 - 12 = 3 (mod 13)
P + a = * * * 2 1 2

El máximo global se producirá en un punto también. Ya que podemos insertar los valores de sufijo de derecha a izquierda, ahora hemos reducido el problema a lo siguiente:

Dado un conjunto de valores S y enteros x y M , encuentre el máximo de S + x módulo M

Este es fácil: solo use un árbol de búsqueda binaria equilibrada para administrar los elementos de S. Dada una consulta x , queremos encontrar el valor más grande en S que sea más pequeño que M - x (ese es el caso en el que no se produce un desbordamiento al agregar x ). Si no hay tal valor, simplemente use el valor más grande de S. Ambos se pueden hacer en tiempo O (log | S |).

Tiempo de ejecución total de esta solución: O (n log n)

Aquí hay un código de C ++ para calcular la suma máxima. Necesitaría algunas adaptaciones menores para devolver también los límites de la subarreglo óptimo:

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

Answer 4

Implementación total de java con 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);

    }

}

Answer 5

Modifique el algoritmo de Kadane para realizar un seguimiento de #currencia. A continuación se muestra el código.

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

Answer 6

Para mí, todas las explicaciones aquí fueron horribles, ya que no obtuve la parte de búsqueda / clasificación. ¿Cómo buscar / ordenar, no estaba claro.

Todos sabemos que necesitamos construir prefixSum , lo que significa la sum of all elems from 0 to i with modulo m

Supongo que lo que buscamos está claro. Sabiendo que el subarray[i][j] = (prefix[i] - prefix[j] + m) % m (que indica la suma de módulo desde el índice i hasta j), nuestro máximo cuando se le da el prefijo [i] es siempre ese prefijo [ j] que está lo más cerca posible del prefijo [i], pero ligeramente más grande.

Por ejemplo, para m = 8, prefijo [i] siendo 5, estamos buscando el siguiente valor después de 5, que está en nuestro prefixArray.

Para una búsqueda eficiente (búsqueda binaria) ordenamos los prefijos.

Lo que no podemos hacer es construir primero el prefixSum, luego iterar de nuevo de 0 a n y buscar el índice en la matriz de prefijos ordenados, porque podemos encontrar un índice y final que es más pequeño que nuestro índice de inicio, que no es bueno.

Por lo tanto, lo que hacemos es iterar de 0 a n para indicar el índice final de nuestra suma máxima de subarreglo potencial y, a continuación, buscar en nuestra matriz de prefijos ordenados (que está vacía al principio) que contiene los prefijos ordenados entre 0 y índice final.

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

Answer 7

Podemos hacer esto de la siguiente manera:

Manteniendo una sum matriz que en el índice ith , contiene la suma del módulo de 0 a ith .

Para cada índice ith , necesitamos encontrar la sub suma máxima que termina en este índice:

Para cada subarray (inicio + 1, i), sabemos que la suma de mod de este sub array es

int a = (sum[i] - sum[start] + M) % M

Por lo tanto, solo podemos lograr una sub-suma mayor que la sum[i] si la sum[start] es mayor que la sum[i] y tan cerca de la sum[i] como sea posible.

Esto se puede hacer fácilmente si utiliza un árbol de búsqueda binario.

Pseudo código:

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;

Complejidad del tiempo: O (n log n)