Máxima suma de subarreglo módulo m

Dada una array de n elementos y un entero m. La tarea es encontrar el valor máximo de la suma de su subarreglo módulo m, es decir, encontrar la suma de cada subarreglo módulo m e imprimir el valor máximo de esta operación de módulo.
Ejemplos: 
 

Input : arr[] = { 3, 3, 9, 9, 5 }
        m = 7
Output : 6
All sub-arrays and their value:
{ 9 } => 9%7 = 2
{ 3 } => 3%7 = 3
{ 5 } => 5%7 = 5
{ 9, 5 } => 14%7 = 2
{ 9, 9 } => 18%7 = 4
{ 3, 9 } => 12%7 = 5
{ 3, 3 } => 6%7 = 6
{ 3, 9, 9 } => 21%7 = 0
{ 3, 3, 9 } => 15%7 = 1
{ 9, 9, 5 } => 23%7 = 2
{ 3, 3, 9, 9 } => 24%7 = 3
{ 3, 9, 9, 5 } => 26%7 = 5
{ 3, 3, 9, 9, 5 } => 29%7 = 1

Input : arr[] = {10, 7, 18}
        m = 13
Output : 12
The subarray {7, 18} has maximum sub-array
sum modulo 13.

Método 1 (Fuerza bruta): 
use la fuerza bruta para encontrar todos los subarreglos de la array dada y encuentre la suma de cada subarreglo mod m y realice un seguimiento del máximo.
Método 2 (enfoque eficiente): 
la idea es calcular la suma de prefijos de la array. Encontramos la suma máxima que termina con cada índice y finalmente devolvemos el máximo general. Para encontrar la suma máxima que termina en un índice, necesitamos encontrar el punto de partida de la suma máxima que termina en i. Los pasos a continuación explican cómo encontrar el punto de inicio.
 

Let prefix sum for index i be prefixi, i.e., 
prefixi = (arr[0] + arr[1] + .... arr[i] ) % m

Let maximum sum ending with i be, maxSumi. 
Let this sum begins with index j.

maxSumi = (prefixi - prefixj + m) % m
                   
From above expression it is clear that the
value of maxSumi becomes maximum when 
prefixj is greater than prefixi 
and closest to prefixi

Principalmente tenemos dos operaciones en el algoritmo anterior. 
 

1. Guarda todos los prefijos.
2. Para el prefijo actual, prefijo _i , busque el valor más pequeño mayor o igual que el prefijo _i + 1.

Para las operaciones anteriores, los árboles de búsqueda binarios autoequilibrados como AVL Tree, Red-Black Tree, etc. son los más adecuados. En la implementación a continuación, usamos set en STL que implementa un árbol de búsqueda binario de autoequilibrio.
A continuación se muestra la implementación de este enfoque: 
 

// C++ program to find sub-array having maximum
// sum of elements modulo m.
#include<bits/stdc++.h>
using namespace std;
 
// Return the maximum sum subarray mod m.
int maxSubarray(int arr[], int n, int m)
{
    int x, prefix = 0, maxim = 0;
 
    set<int> S;
    S.insert(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 = max(maxim, prefix);
 
        // Finding iterator pointing to the first
        // element that is not less than value
        // "prefix + 1", i.e., greater than or
        // equal to this value.
        auto it = S.lower_bound(prefix+1);
 
        if (it != S.end())
            maxim = max(maxim, prefix - (*it) + m );
 
        // Inserting prefix in the set.
        S.insert(prefix);
    }
 
    return maxim;
}
 
// Driver Program
int main()
{
    int arr[] = { 3, 3, 9, 9, 5 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 7;
    cout << maxSubarray(arr, n, m) << endl;
    return 0;
}

// Java program to find sub-array
// having maximum sum of elements modulo m.
import java.util.*;
class GFG
{
 
  // Return the maximum sum subarray mod m.
  static int maxSubarray(int[] arr, int n, int m)
  {
    int x = 0;
    int prefix = 0;
    int maxim = 0;
    Set<Integer> S = new HashSet<Integer>();
    S.add(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 pointing to the first
      // element that is not less than value
      // "prefix + 1", i.e., greater than or
      // equal to this value.
      int it = 0;
 
      for (int j : S)
      {
        if (j >= prefix + 1)
          it = j;
      }
      if (it != 0)
      {
        maxim = Math.max(maxim, prefix - it + m);
      }
 
      // adding prefix in the set.
      S.add(prefix);
    }
    return maxim;
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Driver Code
    int[] arr = new int[] { 3, 3, 9, 9, 5 };
    int n = 5;
    int m = 7;
    System.out.print(maxSubarray(arr, n, m));
  }
}
 
// This code is contributed by pratham76.

# Python3 program to find sub-array
# having maximum sum of elements modulo m.
 
# Return the maximum sum subarray mod m.
def maxSubarray(arr, n, m):
 
    x = 0
    prefix = 0
    maxim = 0
 
    S = set()
    S.add(0)    
 
    # Traversing the array.
    for i in range(n):
 
        # Finding prefix sum.
        prefix = (prefix + arr[i]) % m
 
        # Finding maximum of prefix sum.
        maxim = max(maxim, prefix)
 
        # Finding iterator pointing to the first
        # element that is not less than value
        # "prefix + 1", i.e., greater than or
        # equal to this value.
        it = 0
        for i in S:
            if i >= prefix + 1:
                it = i
        if (it != 0) :
                maxim = max(maxim, prefix - it + m )
 
        # adding prefix in the set.
        S.add(prefix)
 
    return maxim
 
# Driver Code
arr = [3, 3, 9, 9, 5]
n = 5
m = 7
print(maxSubarray(arr, n, m))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# program to find sub-array
// having maximum sum of elements modulo m.
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Return the maximum sum subarray mod m.
  static int maxSubarray(int[] arr, int n, int m)
  {
     
    int prefix = 0;
    int maxim = 0;
    HashSet<int> S = new HashSet<int>();
    S.Add(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 pointing to the first
      // element that is not less than value
      // "prefix + 1", i.e., greater than or
      // equal to this value.
      int it = 0;
 
      foreach(int j in S)
      {
        if (j >= prefix + 1)
          it = j;
      }
      if (it != 0)
      {
        maxim = Math.Max(maxim, prefix - it + m);
      }
 
      // adding prefix in the set.
      S.Add(prefix);
    }
    return maxim;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    int[] arr = new int[] { 3, 3, 9, 9, 5 };
    int n = 5;
    int m = 7;
    Console.Write(maxSubarray(arr, n, m));
  }
}
 
// This code is contributed by rutvik_56.

<script>
// Javascript program to find sub-array
// having maximum sum of elements modulo m.
 
// Return the maximum sum subarray mod m.
function maxSubarray(arr,n,m)
{
    let x = 0;
    let prefix = 0;
    let maxim = 0;
    let S = new Set();
    S.add(0);
  
    // Traversing the array.
    for (let 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 pointing to the first
      // element that is not less than value
      // "prefix + 1", i.e., greater than or
      // equal to this value.
      let it = 0;
  
      for (let j of S.values())
      {
        if (j >= prefix + 1)
          it = j;
      }
      if (it != 0)
      {
        maxim = Math.max(maxim, prefix - it + m);
      }
  
      // adding prefix in the set.
      S.add(prefix);
    }
    return maxim;
}
 
 // Driver Code
let arr=[3, 3, 9, 9, 5];
let n = 5;
let m = 7;
document.write(maxSubarray(arr, n, m));
 
// This code is contributed by avanitrachhadiya2155
</script>

Producción: 
 

6

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar:   O(n)

Referencia: 
http://stackoverflow.com/questions/31113993/maximum-subarray-sum-modulo-m
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.