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

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

Полная реализация 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";
    }
}

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

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

Мы все знаем, что нам нужно построить 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