wake-up-neo.com

Maximale Subarray-Summe Modulo M

Die meisten von uns sind mit dem Maximum Sum Subarray Problem vertraut. Ich bin auf eine Variante dieses Problems gestoßen, die den Programmierer auffordert, das Maximum aller Subarray-Summenmodule einige Zahl M auszugeben. 

Der naive Ansatz zur Lösung dieser Variante besteht darin, alle möglichen Subarray-Summen zu finden (die in der Größenordnung von N ^ 2 liegen würden, wobei N die Größe des Arrays ist). Das ist natürlich nicht gut genug. Die Frage ist - wie können wir besser machen? 

Beispiel: Betrachten wir folgendes Array:

6 6 11 15 12 1 

Sei M = 13. In diesem Fall ergibt das Subarray 6 6 (oder 12 oder 6 6 11 15 oder 11 15 12) eine maximale Summe (= 12). 

26
Bhoot

Wir können dies wie folgt tun:

Unter Beibehaltung eines Arrays sum, das am Index ith die Modulsumme von 0 bis ith enthält.

Für jeden Index ith müssen wir die maximale Zwischensumme finden, die an diesem Index endet:

Für jedes Subarray (Start + 1, i) wissen wir, dass die Modsumme dieses Subarrays ist

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

Wir können also nur eine Teilsumme erreichen, die größer ist als sum[i] wenn sum[start] ist größer als sum[i] und so nah an sum[i] wie möglich.

Dies ist einfach möglich, wenn Sie einen binären Suchbaum verwenden.

Pseudocode:

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;

Zeitkomplexität: O (n log n)

23
Pham Trung

Sei EIN unser Eingabearray mit nullbasierter Indizierung. Wir können A modulo M reduzieren, ohne das Ergebnis zu ändern.

Zunächst reduzieren wir das Problem auf ein etwas einfacheres Problem, indem wir ein Array berechnen P , das die Präfixsummen von A DARSTELLT , modulo M :

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

Verarbeiten wir nun die möglichen linken Ränder unserer Lösungs-Subarrays in absteigender Reihenfolge. Dies bedeutet, dass wir zuerst die optimale Lösung ermitteln, die am Index beginnt n - 1, dann diejenige, die am Index beginnt n - 2 usw.

Wenn wir in unserem Beispiel i = als unseren linken Rand gewählt haben, werden die möglichen Subarraysummen durch das Suffix P [3..n-1] plus einer Konstante dargestellt a = A [i] - P [i]:

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

Das globale Maximum wird auch an einem Punkt auftreten. Da wir die Suffix-Werte von rechts nach links einfügen können, haben wir das Problem jetzt auf Folgendes reduziert:

Ausgehend von einer Reihe von Werten S und ganzen Zahlen x und M , finde das Maximum von S + x modulo M

Dies ist ganz einfach: Verwenden Sie einfach einen ausgewogenen binären Suchbaum, um die Elemente von S zu verwalten. Bei einer gegebenen Abfrage x möchten wir den größten Wert in S finden, der kleiner ist als M - x (das ist der Fall, wenn beim Hinzufügen von x kein Überlauf auftritt). Wenn es keinen solchen Wert gibt, verwenden Sie einfach den größten Wert von S . Beides kann in O (log | S |) erfolgen.

Gesamtlaufzeit dieser Lösung: O (n log n)

Hier ist ein C++ - Code, um die maximale Summe zu berechnen. Es wären einige geringfügige Anpassungen erforderlich, um auch die Ränder des optimalen Subarrays zurückzugeben:

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

Hier ist Java-Code für die maximale Sub-Array-Summe. Wir behandeln den Fall, dass wir nicht das kleinste Element im Baum finden können, das strikt größer ist als 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;
 }
2
The Tran

Wie Sie in Wikipedia nachlesen können, gibt es eine Lösung namens Kadanes Algorithmus, die die maximale Summe der Subarrays berechnet, wobei die maximale Summe der Subarrays bei Position i für alle Positionen i durch einmaliges Durchlaufen des Arrays. Dann ist das Problem mit der Laufzeitkomplexität O (n) gelöst.

Leider denke ich, dass Kadanes Algorithmus nicht alle möglichen Lösungen finden kann, wenn mehr als eine Lösung existiert.

Eine Implementierung in Java habe ich nicht getestet:

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);
    }
1
DAme

Java-Implementierung insgesamt mit 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);

    }

}
1
fatih tekin

Für mich waren alle Erklärungen schrecklich, da ich den Such-/Sortierteil nicht bekam. Wie wir suchen/sortieren, war unklar.

Wir alle wissen, dass wir prefixSum bauen müssen, was sum of all elems from 0 to i with modulo m bedeutet.

Ich schätze, wonach wir suchen, ist klar . Wenn wir wissen, dass subarray[i][j] = (prefix[i] - prefix[j] + m) % m (zeigt die Modulosumme vom Index i bis j an), ist unser Maximum bei gegebenem Präfix [i] immer das Präfix [j], das so nahe wie möglich ist [i] vorangestellt, aber etwas größer.

Z.B. für m = 8, wobei Präfix [i] 5 ist, suchen wir nach 5 den nächsten Wert, der sich in unserem PräfixArray befindet.

Für eine effiziente Suche (binäre Suche) sortieren wir die Präfixe.

Was wir nicht tun können, ist, zuerst das prefixSum zu erstellen, dann erneut von 0 nach n zu itern und nach Index im sortierten Präfixarray zu suchen, da wir endIndex finden können, das kleiner ist als unser startIndex, was nicht gut ist.

Daher iterieren wir von 0 bis n und geben dabei den endIndex unserer potenziellen Max-Subarray-Summe an. Dann schauen wir in unser sortiertes Präfix-Array (das am Anfang leer ist), das sortierte Präfixe zwischen 0 und endIndex enthält .

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
1
denis631

Hinzufügen von STL C++ 11-Code basierend auf der von @Pham Trung vorgeschlagenen Lösung. Könnte nützlich sein. 

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