算法：m个范围增量操作后数组中的最大值

本文概述

• C++
• Java
• Python3
• C ++
• Java

考虑一个大小为n的数组，所有初始值都为0，我们需要执行以下m个范围递增操作。

increment(a, b, k) : Increment values from 'a'
                     to 'b' by 'k'.

经过m次运算后, 我们需要计算数组中的最大值。

例子：

Input : n = 5 m = 3
        a = 0, b = 1, k = 100
        a = 1, b = 4, k = 100
        a = 2, b = 3, k = 100
Output : 200
Explanation:
Initially array = {0, 0, 0, 0, 0}
After first operation:
array = {100, 100, 0, 0, 0}
After second operation:
array = {100, 200, 100, 100, 100}
After third operation:
array = {100, 200, 200, 200, 100}
Maximum element after m operations 
is 200.

Input : n = 4 m = 3
        a = 1, b = 2, k = 603
        a = 0, b = 0, k = 286
        a = 3, b = 3, k = 882
Output : 882
Explanation:
Initially array = {0, 0, 0, 0}
After first operation:
array = {0, 603, 603, 0}
After second operation:
array = {286, 603, 603, 0}
After third operation:
array = {286, 603, 603, 882}
Maximum element after m operations 
is 882.

一种天真的方法是在给定范围内执行每个操作, 然后最后找到最大数量。

C++

// C++ implementation of simple approach to
// find maximum value after m range increments.
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the maximum element after
// m operations
int findMax( int n, int a[], int b[], int k[], int m)
{
     int arr[n];
     memset (arr, 0, sizeof (arr));
 
     // start performing m operations
     for ( int i = 0; i< m; i++)
     {
         // Store lower and upper index i.e. range
         int lowerbound = a[i];
         int upperbound = b[i];
 
         // Add 'k[i]' value at this operation to
         // whole range
         for ( int j=lowerbound; j<=upperbound; j++)
             arr[j] += k[i];
     }
 
     // Find maximum value after all operations and
     // return
     int res = INT_MIN;
     for ( int i=0; i<n; i++)
         res = max(res, arr[i]);
 
     return res;
}
 
// Driver code
int main()
{
     // Number of values
     int n = 5;
     int a[] = {0, 1, 2};
     int b[] = {1, 4, 3};
 
     // value of k to be added at each operation
     int k[] = {100, 100, 100};
 
     int m = sizeof (a)/ sizeof (a[0]);
 
     cout << "Maximum value after 'm' operations is "
         << findMax(n, a, b, k, m);
     return 0;
}

Java

// Java implementation of simple approach
// to find maximum value after m range
// increments.
import java.util.*;
 
class GFG{
     
// Function to find the maximum element after
// m operations
static int findMax( int n, int a[], int b[], int k[], int m)
{
     int [] arr = new int [n];
 
     // Start performing m operations
     for ( int i = 0 ; i < m; i++)
     {
         
         // Store lower and upper index i.e. range
         int lowerbound = a[i];
         int upperbound = b[i];
 
         // Add 'k[i]' value at this operation to
         // whole range
         for ( int j = lowerbound; j <= upperbound; j++)
             arr[j] += k[i];
     }
 
     // Find maximum value after all
     // operations and return
     int res = Integer.MIN_VALUE;
     for ( int i = 0 ; i < n; i++)
         res = Math.max(res, arr[i]);
 
     return res;
}
 
// Driver Code
public static void main (String[] args)
{
     
     // Number of values
     int n = 5 ;
     int a[] = { 0 , 1 , 2 };
     int b[] = { 1 , 4 , 3 };
     
     // Value of k to be added at
     // each operation
     int k[] = { 100 , 100 , 100 };
     
     int m = a.length;
     
     System.out.println( "Maximum value after 'm' " +
                        "operations is " +
                        findMax(n, a, b, k, m));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 progrma of
# simple approach to
# find maximum value
# after m range increments.
import sys
 
# Function to find the
# maximum element after
# m operations
def findMax(n, a, b, k, m):
 
   arr = [ 0 ] * n
 
   # Start performing m operations
   for i in range (m):
     
     # Store lower and upper
     # index i.e. range
     lowerbound = a[i]
     upperbound = b[i]
 
     # Add 'k[i]' value at
     # this operation to whole range
     for j in range (lowerbound, upperbound + 1 ):
       arr[j] + = k[i]
 
       # Find maximum value after
       # all operations and return
       res = - sys.maxsize - 1
       
       for i in range (n):
         res = max (res, arr[i])
         return res
  
# Driver code
if __name__ = = "__main__" :
 
   # Number of values
   n = 5
   a = [ 0 , 1 , 2 ]
   b = [ 1 , 4 , 3 ]
 
   # Value of k to be added
   # at each operation
   k = [ 100 , 100 , 100 ]
 
   m = len (a)
 
   print ( "Maximum value after 'm' operations is " , findMax(n, a, b, k, m))
  
# This code is contributed by Chitranayal

输出如下：

Maximum value after 'm' operations is 200

时间复杂度：O(m * max(range))。此处的max(range)表示在单个操作中将k添加到的最大元素。

高效的方法：

这个想法类似于

这个

发布。

只需一次操作即可完成两件事：

1-将k值添加到范围的lower_bound。

2-通过k值减少upper_bound +1索引。

毕竟, 进行操作, 将所有值相加, 检查最大和, 然后打印最大和。

C++

// C++ implementation of simple approach to
// find maximum value after m range increments.
#include<bits/stdc++.h>
using namespace std;
 
// Function to find maximum value after 'm' operations
int findMax( int n, int m, int a[], int b[], int k[])
{
     int arr[n+1];
     memset (arr, 0, sizeof (arr));
 
     // Start performing 'm' operations
     for ( int i=0; i<m; i++)
     {
         // Store lower and upper index i.e. range
         int lowerbound = a[i];
         int upperbound = b[i];
 
         // Add k to the lower_bound
         arr[lowerbound] += k[i];
 
         // Reduce upper_bound+1 indexed value by k
         arr[upperbound+1] -= k[i];
     }
 
     // Find maximum sum possible from all values
     long long sum = 0, res = INT_MIN;
     for ( int i=0; i < n; ++i)
     {
         sum += arr[i];
         res = max(res, sum);
     }
 
     // return maximum value
     return res;
}
 
// Driver code
int main()
{
     // Number of values
     int n = 5;
 
     int a[] = {0, 1, 2};
     int b[] = {1, 4, 3};
     int k[] = {100, 100, 100};
 
     // m is number of operations.
     int m = sizeof (a)/ sizeof (a[0]);
 
     cout << "Maximum value after 'm' operations is "
          << findMax(n, m, a, b, k);
     return 0;
}

Java

// Java implementation of
// simple approach to
// find maximum value after
// m range increments.
import java.io.*;
 
class GFG
{
     
// Function to find maximum
// value after 'm' operations
static long findMax( int n, int m, int a[], int b[], int k[])
{
     int []arr = new int [n + 1 ];
     //memset(arr, 0, sizeof(arr));
 
     // Start performing 'm' operations
     for ( int i = 0 ; i < m; i++)
     {
         // Store lower and upper
         // index i.e. range
         int lowerbound = a[i];
         int upperbound = b[i];
 
         // Add k to the lower_bound
         arr[lowerbound] += k[i];
 
         // Reduce upper_bound+1
         // indexed value by k
         arr[upperbound + 1 ] -= k[i];
     }
 
     // Find maximum sum
     // possible from all values
     long sum = 0 , res = Integer.MIN_VALUE;
     for ( int i = 0 ; i < n; ++i)
     {
         sum += arr[i];
         res = Math.max(res, sum);
     }
 
     // return maximum value
     return res;
}
 
// Driver code
public static void main (String[] args)
{
     // Number of values
     int n = 5 ;
     
     int a[] = { 0 , 1 , 2 };
     int b[] = { 1 , 4 , 3 };
     int k[] = { 100 , 100 , 100 };
     
     // m is number of operations.
     int m = a.length;
     
     System.out.println( "Maximum value after " +
                         "'m' operations is " +
                       findMax(n, m, a, b, k));
     }
}
 
// This code is contributed by anuj_67.

输出如下：

Maximum value after 'm' operations is 200