Maximum subarray sum modulo M
The maximum subarray sum modulo M problem is a popular programming challenge that involves finding the maximum sum of a contiguous subarray from a given array, where the sum is taken modulo M. This problem has various real-world applications, such as financial analysis, data processing, and optimization algorithms. In this article, we will discuss the problem statement, provide a detailed explanation of the algorithmic approach, and implementation.
Problem Statement:
Given an array of integers and a positive integer M, the task is to find the maximum sum of a subarray modulo M. The subarray sum modulo M is calculated by taking the sum of elements in the subarray and finding the remainder when divided by M. The goal is to determine the maximum value among all possible subarray sums modulo M.
Algorithmic Approach:
To solve this problem efficiently, we can utilize the concept of prefix sums and sets. Here's an overview of the algorithm:
- Initialize variables: prefix = 0, max = 0, and an empty set called record.
- Insert 0 into the record set since it represents an empty subarray sum modulo M.
- Iterate through the array elements:
a. Update the prefix sum by adding the current element and taking the modulo M.
b. Update the maximum value by comparing the current prefix sum with the previous maximum value.
c. Use a lower_bound operation on the record set to find the first element greater than the current prefix sum + 1.
- If a suitable element is found, update the maximum value by comparing it with prefix - (*v) + M, where v is the found element. d. Insert the current prefix sum into the record set.
- After iterating through all array elements, the maximum subarray sum modulo M is stored in the max variable.
Detailed Explanation:
Let's understand the algorithm step-by-step with the help of an example:
Consider the array: [4, 3, 2, 3, 7, 2] and M = 7.
Initialize prefix = 0, max = 0, and an empty set called record.
- record: {}
Insert 0 into the record set.
- record: {0}
Iterate through the array elements:
i = 0:
- prefix = (0 + 4) % 7 = 4
- max = max(0, 4) = 4
- record: {0, 4}
i = 1:
- prefix = (4 + 3) % 7 = 0
- max = max(4, 0) = 4
- v = record.lower_bound(0 + 1) = record.lower_bound(1) = record.begin()
- No suitable element found.
- record: {0, 4}
i = 2:
- prefix = (0 + 2) % 7 = 2
- max = max(4, 2) = 4
- v = record.lower_bound(2 + 1) = record.lower_bound(3) = record.begin()
- No suitable element found.
- record: {0, 2, 4}
i = 3:
- prefix = (2 + 3) % 7 = 5
- max = max(4, 5) = 5
- v = record.lower_bound(5 + 1) = record.lower_bound(6) = record.begin()
- No suitable element found.
- record: {0, 2, 4, 5}
i = 4:
- prefix = (5 + 7) % 7 = 5
- max = max(5, 5) = 5
- v = record.lower_bound(5 + 1) = record.lower_bound(6) = record.end()
- No suitable element found.
- record: {0, 2, 4, 5}
i = 5:
- prefix = (5 + 2) % 7 = 0
- max = max(5, 0) = 5
- v = record.lower_bound(0 + 1) = record.lower_bound(1) = record.begin()
- max = max(5, 0 - (*v) + 7) = max(5, 0 - 0 + 7) = 5
- record: {0, 2, 4, 5}
The maximum subarray sum modulo M is stored in the max variable.
- Result: 5
Code Solution
// Include header file
#include <iostream>
#include <set>
using namespace std;
/*
C++ Program for
Maximum subarray sum modulo M
*/
class MaximumSubarray
{
public:
// Print array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void maxModuloMSubArray(int arr[], int n, int m)
{
int prefix = 0;
int max = 0;
set < int > record;
// Add first element in record
record.insert(0);
for (int i = 0; i < n; ++i)
{
prefix = (prefix + arr[i]) % m;
max = this->maxValue(max, prefix);
auto v = record.lower_bound(prefix+1);
if (v != record.end())
{
max = this->maxValue(max, prefix -
(*v) + m);
}
// Add prefix into record
record.insert(prefix);
}
// Display calculated result
cout << "Result : " << max;
}
};
int main()
{
MaximumSubarray *task = new MaximumSubarray();
int arr[] = {
4 , 3 , 2 , 3 , 7 , 2
};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 7;
/*
M = 7
arr = [4 ,3, 2, 3, 7, 2]
All subarray
---------------------------------------------------
[ 4 ] = [4] % 7 => 4
[ 4 + 3 ] = [7] % 7 => 0
[ 4 + 3 + 2 ] = [9] % 7 => 2
[ 4 + 3 + 2 + 3 ] = [12] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 ] = [19] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 + 2 ] = [21] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 2 ] = [5] % 7 => 5
[ 3 + 2 + 3 ] = [8] % 7 => 1
[ 3 + 2 + 3 + 7 ] = [15] % 7 => 1
[ 3 + 2 + 3 + 7 + 2 ] = [17] % 7 => 3
[ 2 ] = [2] % 7 => 2
[ 2 + 3 ] = [5] % 7 => 5
[ 2 + 3 + 7 ] = [12] % 7 => 5
[ 2 + 3 + 7 + 2 ] = [14] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 7 ] = [10] % 7 => 3
[ 3 + 7 + 2 ] = [12] % 7 => 5
[ 7 ] = [7] % 7 => 0
[ 7 + 2 ] = [9] % 7 => 2
[ 2 ] = [2] % 7 => 2
-----------------------------------------------------
Result : 5
*/
task->maxModuloMSubArray(arr, n, m);
return 0;
}Output
Result : 5// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program for
Maximum subarray sum modulo M
*/
public class MaximumSubarray
{
// Print array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxModuloMSubArray(int[] arr, int n, int m)
{
int prefix = 0;
int max = 0;
SortedSet < int > record = new SortedSet < int > ();
// Add first element in record
record.Add(0);
for (int i = 0; i < n; ++i)
{
prefix = (prefix + arr[i]) % m;
max = this.maxValue(max, prefix);
if (record.Max > prefix + 1)
{
SortedSet < int > ans =
record.GetViewBetween(prefix + 1, record.Max);
if (ans.Count > 0)
{
max = this.maxValue(max, prefix - (ans.Min) + m);
}
}
// Add prefix into record
record.Add(prefix);
}
// Display calculated result
Console.Write("Result : " + max);
}
public static void Main(String[] args)
{
MaximumSubarray task = new MaximumSubarray();
int[] arr = {
4 , 3 , 2 , 3 , 7 , 2
};
int n = arr.Length;
int m = 7;
/*
M = 7
arr = [4 ,3, 2, 3, 7, 2]
All subarray
---------------------------------------------------
[ 4 ] = [4] % 7 => 4
[ 4 + 3 ] = [7] % 7 => 0
[ 4 + 3 + 2 ] = [9] % 7 => 2
[ 4 + 3 + 2 + 3 ] = [12] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 ] = [19] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 + 2 ] = [21] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 2 ] = [5] % 7 => 5
[ 3 + 2 + 3 ] = [8] % 7 => 1
[ 3 + 2 + 3 + 7 ] = [15] % 7 => 1
[ 3 + 2 + 3 + 7 + 2 ] = [17] % 7 => 3
[ 2 ] = [2] % 7 => 2
[ 2 + 3 ] = [5] % 7 => 5
[ 2 + 3 + 7 ] = [12] % 7 => 5
[ 2 + 3 + 7 + 2 ] = [14] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 7 ] = [10] % 7 => 3
[ 3 + 7 + 2 ] = [12] % 7 => 5
[ 7 ] = [7] % 7 => 0
[ 7 + 2 ] = [9] % 7 => 2
[ 2 ] = [2] % 7 => 2
-----------------------------------------------------
Result : 5
*/
task.maxModuloMSubArray(arr, n, m);
}
}Output
Result : 5import java.util.TreeSet;
/*
Java Program for
Maximum subarray sum modulo M
*/
public class MaximumSubarray
{
// Print array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void maxModuloMSubArray(int[] arr, int n, int m)
{
int prefix = 0;
int max = 0;
TreeSet < Integer > record = new TreeSet < Integer > ();
// Add first element in record
record.add(0);
for (int i = 0; i < n; ++i)
{
prefix = (prefix + arr[i]) % m;
max = maxValue(max, prefix);
if (record.higher(prefix) != null)
{
max = maxValue(max, prefix - (record.higher(prefix)) + m);
}
// Add prefix into record
record.add(prefix);
}
// Display calculated result
System.out.print("Result : " + max);
}
public static void main(String[] args)
{
MaximumSubarray task = new MaximumSubarray();
int[] arr = {
4 , 3 , 2 , 3 , 7 , 2
};
int n = arr.length;
int m = 7;
/*
M = 7
arr = [4 ,3, 2, 3, 7, 2]
All subarray
---------------------------------------------------
[ 4 ] = [4] % 7 => 4
[ 4 + 3 ] = [7] % 7 => 0
[ 4 + 3 + 2 ] = [9] % 7 => 2
[ 4 + 3 + 2 + 3 ] = [12] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 ] = [19] % 7 => 5
[ 4 + 3 + 2 + 3 + 7 + 2 ] = [21] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 2 ] = [5] % 7 => 5
[ 3 + 2 + 3 ] = [8] % 7 => 1
[ 3 + 2 + 3 + 7 ] = [15] % 7 => 1
[ 3 + 2 + 3 + 7 + 2 ] = [17] % 7 => 3
[ 2 ] = [2] % 7 => 2
[ 2 + 3 ] = [5] % 7 => 5
[ 2 + 3 + 7 ] = [12] % 7 => 5
[ 2 + 3 + 7 + 2 ] = [14] % 7 => 0
[ 3 ] = [3] % 7 => 3
[ 3 + 7 ] = [10] % 7 => 3
[ 3 + 7 + 2 ] = [12] % 7 => 5
[ 7 ] = [7] % 7 => 0
[ 7 + 2 ] = [9] % 7 => 2
[ 2 ] = [2] % 7 => 2
-----------------------------------------------------
Result : 5
*/
task.maxModuloMSubArray(arr, n, m);
}
}Output
Result : 5
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment