Maximum subarray sum modulo M
Here given code implementation process.
// 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