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

2021年3月28日12:06:50 发表评论 388 次浏览

## 本文概述

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

``````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]

# 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``

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``