Accumulate Maximum

The accumulate maximum problem involves finding the maximum element in a given range of an array. This is similar to range sum, except instead of summing, we find the maximum value.

Some example code:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Find max in range [i, j]
int accumulateMax(int[] nums, int i, int j) {
  
  int max = Integer.MIN_VALUE;
  
  for (int k = i; k <= j; k++) {
    if (nums[k] > max) {
      max = nums[k];
    }
  }
  
  return max;
}

int[] nums = {2, 5, 3, 8, 10};
int max = accumulateMax(nums, 1, 3); // Returns 8

C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// Find max in range [i, j] 
int accumulateMax(vector<int>& nums, int i, int j) {

  int max = INT_MIN;
  
  for (int k = i; k <= j; k++) {
    if (nums[k] > max) {
      max = nums[k];
    }
  }

  return max;
}

vector<int> nums{2, 5, 3, 8, 10};
int max = accumulateMax(nums, 1, 3); // Returns 8

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Find max in range [i, j]
def accumulate_max(nums, i, j):
  
  max_val = float("-inf")
  
  for k in range(i, j+1):
    if nums[k] > max_val:
      max_val = nums[k]
      
  return max_val

nums = [2, 5, 3, 8, 10]  
max = accumulate_max(nums, 1, 3) # Returns 8

The key steps are:

Initialize a variable to keep track of maximum
Iterate through the range, updating max if element is greater
Return the maximum

This allows finding the maximum element in a specified subarray range efficiently.

The Accumulate Maximum operation involves calculating the maximum value for each position in an array up to that point. Here’s how to perform this task:

Description:

Given an array of integers, the task is to calculate the Accumulate Maximum.

Java:

In Java, you can calculate the Accumulate Maximum by iterating through the array from left to right.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class AccumulateMaxCalculator {
    public static int[] accumulateMax(int[] numbers) {
        int[] accumulateMax = new int[numbers.length];
        accumulateMax[0] = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            accumulateMax[i] = Math.max(accumulateMax[i - 1], numbers[i]);
        }
        return accumulateMax;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40};
        int[] result = accumulateMax(numbers);
        for (int number : result) {
            System.out.print(number + " "); // Output: 10 20 30 40
        }
    }
}

C++:

In C++, you can calculate the Accumulate Maximum similarly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> accumulateMax(std::vector<int>& numbers) {
    std::vector<int> accumulateMax(numbers.size());
    accumulateMax[0] = numbers[0];
    for (int i = 1; i < numbers.size(); i++) {
        accumulateMax[i] = std::max(accumulateMax[i - 1], numbers[i]);
    }
    return accumulateMax;
}

int main() {
    std::vector<int> numbers = {10, 20, 30, 40};
    std::vector<int> result = accumulateMax(numbers);
    for (int number : result) {
        std::cout << number << " "; // Output: 10 20 30 40
    }
    return 0;
}

Python:

In Python, the Accumulate Maximum can be calculated using similar logic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def accumulate_max(numbers):
    accumulate_max = [0] * len(numbers)
    accumulate_max[0] = numbers[0]
    for i in range(1, len(numbers)):
        accumulate_max[i] = max(accumulate_max[i - 1], numbers[i])
    return accumulate_max

numbers = [10, 20, 30, 40]
result = accumulate_max(numbers)
print(result) # Output: [10, 20, 30, 40]

These examples cover calculating the Accumulate Maximum for an array of integers in Java, C++, and Python. They create a new array where each value is the maximum value of the original array’s values up to that index.

Tabular Representation

Here’s a table that demonstrates what happens in each iteration for the input array [10, 20, 30, 40].

Iteration	Current Element	Accumulate Maximum So Far	Resulting Accumulate Maximum Array
0	10	10	[10, -, -, -]
1	20	20	[10, 20, -, -]
2	30	30	[10, 20, 30, -]
3	40	40	[10, 20, 30, 40]

Explanation:

Iteration 0: The first element is 10, so the accumulate maximum is 10.
Iteration 1: The next element is 20, so the accumulate maximum is 20.
Iteration 2: The next element is 30, so the accumulate maximum is 30.
Iteration 3: The next element is 40, so the accumulate maximum is 40.

The resulting accumulate maximum array is [10, 20, 30, 40], which represents the maximum value at each position in the array up to that point.