Maximize Array Sum Except Elements From [i, i + A] for all i Such That ARR[i] > B

Approach

We are going to solve this problem using a greedy approach.

• First, we will create two vectors(containers) named smaller and greater. 
• In smaller, we will store elements smaller than B, and in greater, we will store elements greater than B.
• Now, let's talk about one observation here.
• To get the maximum sum, we must include i elements greater than B in the summation. To include these i  elements in the sum,        there must be (i − 1)(A + 1) + 1 elements in the array.

For example, let's say A=2.

And we want two elements that are greater than B=10 in the summation.

This is the example we already discussed.

So according to the formula,

If i=2, A=2; then at least (2-1)(2+1) + 1 = 4 elements should be present in the array.

This means,

• Now, as we can see that if the number of elements greater than B that must be included in the answer ‘MAX_SUM’ is, let's say, ‘i’, then by maths, there must exist at least ((i - 1) * (A + 1) + 1) - i smallest elements in the array ‘ARR.’
• So we iterate for each possible i, we can exclude the ((i - 1) * (A + 1) + 1) - i smallest elements of that of the smaller vector from the answer ‘MAX_SUM.’
• Note: In our example array, we could skip any two elements, but to get the maximum, we must skip the smallest elements for each i. The above step is to achieve that goal.
• The maximum value that can occur over each possible sum for each ‘i’ is the required result.

Program 

You can follow the C++ and Python code for this problem.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;

// Function sorts the vector in reverse order and finds the prefix sum of the vector.
void prefixSum(vector<int> &vec)
{
  // Sorts the vector in descending order.
  sort(vec.begin() + 1, vec.end(), [](int &a, int &b)
        { return a > b; });

  // Finds the prefix sum.
  for (int i = 1; i < vec.size(); i++)
  {
      vec[i] += vec[i - 1];
  }
}

// Function that maximises array sum except for elements from [i, i + A] for all i such that arr[i] > B.
int calculateMaxSum(vector<int> &arr, int a, int b)
{
  int n = arr.size();

  // Declare a vector to store elements greater and smaller than 'B.'
  vector<int> smaller{0}, greater{0};

  // Iterate over the array and insert all elements greater than 'B' into 'GREATER' vector and all elements smaller than 'B' into 'SMALLER' vector.
  for (int i = 0; i < n; i++)
  {
      if (arr[i] > b)
      {
          greater.emplace_back(arr[i]);
      }
      else
      {
          smaller.emplace_back(arr[i]);
      }
  }

  // Size of both vectors.
  int smallerSize = smaller.size();
  int greaterSize = greater.size();

  // If 'B' is 0 then return the sum of all elements in 'SMALLER'.
  if (greaterSize == 0)
  {
      return accumulate(smaller.begin(), smaller.end(), 0);
  }

  // Now reverse these arrays and sort them in descending order, then find prefix sum.
  prefixSum(greater);
  prefixSum(smaller);

  // Resize the 'SMALLER' vector to size N + 1 and fill it with the size of a smaller vector.
  smaller.resize(n + 1);
  fill(smaller.begin() + smallerSize - 1, smaller.end(), smaller[smallerSize - 1]);

  // Initialize MAX_SUM.
  int maxSum = 0;

  // Now for all 'i' in greater array, exclude first (A + 1)(i + 1) - i elements from 'SMALLER'.
  for (int i = (greaterSize + a) / (1 + a); i <= greaterSize; i++)
  {
      if (1ll * (i - 1) * (a + 1) + 1 <= n)
      {
          maxSum = max(maxSum, greater[i] + smaller[n - 1ll * (i - 1) * (a + 1) - 1]);
      }
  }

  // Return MAX_SUM.
  return maxSum;
}

int main()
{
  int n, a, b;
  cout << "Enter the values of N, A, B: ";
  cin >> n >> a >> b;

  vector<int> arr(n);

  cout << "Enter the elements of the array: ";
  for (int i = 0; i < n; i++)
  {
      cin >> arr[i];
  }

  int maxSum = calculateMaxSum(arr, a, b);

  cout << "Maximum sum that can be achieved is: " << maxSum << endl;

  return 0;

You can also try this code with Online C++ Compiler

Run Code

Java Code

import java.util.*;

public class Main {

    // Function sorts the list in reverse order and finds the prefix sum of the list.
    public static void prefixSum(List<Integer> arr) {
        // Sorts the list in descending order.
        Collections.sort(arr.subList(1, arr.size()), Collections.reverseOrder());

        // Finds the prefix sum.
        for (int i = 1; i < arr.size(); i++) {
            arr.set(i, arr.get(i) + arr.get(i - 1));
        }
    }

    // Function that maximizes list sum except elements from [i, i + A] for all i such that arr[i] > B.
    public static int calculateMaxSum(List<Integer> arr, int a, int b) {
        int n = arr.size();

        // Declare a list to store elements greater and smaller than 'B'.
        List<Integer> smaller = new ArrayList<>(Collections.singletonList(0));
        List<Integer> greater = new ArrayList<>(Collections.singletonList(0));

        // Iterate over the list and insert all elements greater than 'B' into 'GREATER' list and all elements smaller than 'B' into 'SMALLER' list.
        for (int i = 0; i < n; i++) {
            if (arr.get(i) > b) {
                greater.add(arr.get(i));
            } else {
                smaller.add(arr.get(i));
            }
        }

        // Size of both lists.
        int smallerSize = smaller.size();
        int greaterSize = greater.size();

        // If 'B' is 0 then return the sum of all elements in 'SMALLER'.
        if (greaterSize == 1) {
            return smaller.stream().mapToInt(Integer::intValue).sum();
        }

        // Now reverse these lists and sort them in descending order, then find prefix sum.
        prefixSum(greater);
        prefixSum(smaller);

        // Resize the 'SMALLER' list to size N + 1 and fill it with the size of a smaller list.
        smaller.addAll(Collections.nCopies(n - smallerSize + 1, smaller.get(smallerSize - 1)));

        // Initialize MAX_SUM.
        int maxSum = 0;

        // Now for all 'i' in greater list, exclude first (A + 1)(i - 1) - i elements from 'SMALLER'.
        for (int i = (greaterSize + a) / (1 + a); i <= greaterSize; i++) {
            if ((i - 1) * (a + 1) + 1 <= n) {
                maxSum = Math.max(maxSum, greater.get(i) + smaller.get(n - (i - 1) * (a + 1) - 1));
            }
        }

        // Return MAX_SUM.
        return maxSum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the values of N, A, B: ");
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        List<Integer> arr = new ArrayList<>();
        System.out.print("Enter the elements of the array: ");
        for (int i = 0; i < n; i++) {
            arr.add(scanner.nextInt());
        }

        int maxSum = calculateMaxSum(arr, a, b);
        System.out.println("Maximum sum that can be achieved is: " + maxSum);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python Code

from typing import List

# Function sorts the list in reverse order and finds the prefix sum of the list.
def prefix_sum(arr: List[int]) -> None:
    # Sorts the list in descending order.
    arr[1:] = sorted(arr[1:], reverse=True)

    # Finds the prefix sum.
    for i in range(1, len(arr)):
        arr[i] += arr[i-1]

# Function that maximises list sum except elements from [i, i + A] for all i such that arr[i] > B.
def calculate_max_sum(arr: List[int], a: int, b: int) -> int:
    n = len(arr)

    # Declare a list to store elements greater and smaller than 'B'.
    smaller = [0]
    greater = [0]

    # Iterate over the list and insert all elements greater than 'B' into 'GREATER' list and all elements smaller than 'B' into 'SMALLER' list.
    for i in range(n):
        if arr[i] > b:
            greater.append(arr[i])
        else:
            smaller.append(arr[i])

    # Size of both lists.
    smaller_size = len(smaller)
    greater_size = len(greater)

    # If 'B' is 0 then return the sum of all elements in 'SMALLER'.
    if greater_size == 1:
        return sum(smaller)

    # Now reverse these lists and sort them in descending order, then find prefix sum.
    prefix_sum(greater)
    prefix_sum(smaller)

    # Resize the 'SMALLER' list to size N + 1 and fill it with the size of a smaller list.
    smaller += [smaller[smaller_size - 1]] * (n - smaller_size + 1)

    # Initialize MAX_SUM.
    max_sum = 0

    # Now for all 'i' in greater list, exclude first (A + 1)(i - 1) - i elements from 'SMALLER'.
    for i in range((greater_size + a) // (1 + a), greater_size + 1):
        if (i - 1) * (a + 1) + 1 <= n:
            max_sum = max(max_sum, greater[i] + smaller[n - (i - 1) * (a + 1) - 1])

    # Return MAX_SUM.
    return max_sum

if __name__ == '__main__':
    n, a, b = map(int, input("Enter the values of N, A, B: ").split())
    arr = list(map(int, input("Enter the elements of the array: ").split()))

    max_sum = calculate_max_sum(arr, a, b)

    print("Maximum sum that can be achieved is:", max_sum)

Input

Enter the value of N, A, and B: 6 2 10
Enter the elements of the array: 5 6 32 9 8 20

Output

The maximum Sum that can be achieved is: 69

Time Complexity

O(N*log(N)), where ‘N’ is the size of array ‘ARR.’

We are sorting both ‘SMALLER’ and ‘GREATER’ vectors which can have a maximum size of ‘N.’ Hence the time complexity = O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the array ‘ARR’ size.

We declare two vectors, ‘SMALLER’ and ‘GREATER’ of Size ‘N.’

Check out this problem - Search In Rotated Sorted Array

Frequently Asked Questions

What is the difference between pass by value and pass by reference in C++?

In pass by value, a copy of the argument is passed to the function, while in pass by reference, the actual argument is passed to the function. Pass by reference is more efficient and allows for modifications to the original argument.

What is virtual inheritance? 

Virtual inheritance is a mechanism in C++ where a class can inherit from a base class that has multiple inheritances. It allows for the elimination of duplicate base classes in the derived class hierarchy.

What is a smart pointer in C++? 

A smart pointer in C++ is a wrapper class that provides automatic memory management for objects allocated on the heap, preventing memory leaks and improving program efficiency.

What is the difference between a static member and a non-static member? 

A static member belongs to the class and is shared by all objects of that class, while a non-static member belongs to a specific object of the class.

Conclusion

In this article, we discussed the problem of Maximize Array sum except for elements from [i, i+X] for all i such that arr[i] > K and the approach to solving it. We discussed the C++ and Python code to solve it.

I hope you enjoyed this blog.

Check out other related articles to learn more: 

• Array
• Introduction to Array

And many more on our platform Coding Ninjas Studio

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!