Skip to main content

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 : 5
import 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




Comment

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