Maximize Array sum except elements from [i, i+X] for all i such that arr[i] > K
Given an array arr[] of size N and two integers X and K, the task is to find the maximum score that can be achieved by rearranging the elements of the array where the score is calculated as the sum of elements of the array except the next X elements from the index i such arr[i] > K for all possible values of i in the range [0, N).
Example:
Input: arr[] = {9, 13, 16, 21, 6}, X = 2, K = 15
Output: 50
Explanation: The given array can be rearranged as arr[] = {16, 6, 9, 13, 21}. The indices such that arr[i] > K are {0, 4}. Therefore, the next two elements from index 0 and index 4 will be skipped. Therefore, the sum of remaining elements becomes 16 + 13 + 21 = 50, which is the maximum possible.Input: arr[] = {31, 20, 19, 23, 34, 21, 37}, X = 3, K= 22
Output: 112
Approach: The given problem can be solved using a greedy approach. Create two arrays, big[] containing integers greater than K and small[] containing integers smaller than K. It can be observed that if the number of elements greater than K that must be included in the sum is i, then there must exist at least (i − 1)(X + 1) + 1 elements in the array. Hence for each possible i, exclude the ((i − 1)(X + 1) + 1) – i smallest elements of the small[] array from the total sum. The maximum value over all possible sums for each i is the required result.
Below is the implementation of the above approach:
C++
// C++ program, for the above approach #include <bits/stdc++.h> using namespace std; const int maxn = 1e5; // Utility function to calculate the // sum of elements as a prefix array void calc( int arr[], int N) { sort(arr + 1, arr + N + 1); reverse(arr + 1, arr + N + 1); for ( int i = 1; i <= N; i++) { arr[i] += arr[i - 1]; } } // Function to find the maximum score // that can be achieved by rearranging // the elements of given array int maxScore( int arr[], int X, int K, int N) { // Arrays to store small and big elements int small[maxn + 5], big[maxn + 5]; int k = 0, l = 0; // Iterate and segregate big and // small elements for ( int i = 0; i < N; i++) { if (arr[i] > K) { big[++k] = arr[i]; } else { small[++l] = arr[i]; } } // If k = 0, return the sum // of small[] if (k == 0) { int sum = 0; for ( int i = 1; i <= N; i++) { sum += small[i]; } return sum; } // Prefix sums of small[] // and big[] calc(big, k); calc(small, l); // Initialize small[l] within the range fill(small + l + 1, small + N + 1, small[l]); // Variable to store the answer int res = 0; for ( int i = (k + X) / (1 + X); i <= k; i++) { if (1ll * (i - 1) * (X + 1) + 1 <= N) { // Update res with maximum one res = max( res, big[i] + small[N - 1ll * (i - 1) * (X + 1) - 1]); } } // Return res return res; } // Driver Code int main() { int arr[] = { 9, 13, 16, 21, 6 }; int X = 2; int K = 15; int N = sizeof (arr) / sizeof (arr[0]); cout << maxScore(arr, X, K, N); return 0; } |
Java
// Java program, for the above approach import java.util.*; class GFG{ static int maxn = ( int )1e5; // Utility function to calculate the // sum of elements as a prefix array static void calc( int arr[], int N) { Arrays.sort(arr); arr = reverse(arr); for ( int i = 1 ; i <= N; i++) { arr[i] += arr[i - 1 ]; } } static int [] reverse( int a[]) { int i, n = a.length + 1 , t; for (i = 1 ; i < n / 2 ; i++) { t = a[i]; a[i] = a[n - i - 1 ]; a[n - i - 1 ] = t; } return a; } // Function to find the maximum score // that can be achieved by rearranging // the elements of given array static int maxScore( int arr[], int X, int K, int N) { // Arrays to store small and big elements int []small = new int [maxn + 5 ]; int big[] = new int [maxn + 5 ]; int k = 0 , l = 0 ; // Iterate and segregate big and // small elements for ( int i = 0 ; i < N; i++) { if (arr[i] > K) { big[++k] = arr[i]; } else { small[++l] = arr[i]; } } // If k = 0, return the sum // of small[] if (k == 0 ) { int sum = 0 ; for ( int i = 1 ; i <= N; i++) { sum += small[i]; } return sum; } // Prefix sums of small[] // and big[] calc(big, k); calc(small, l); // Initialize small[l] within the range // fill(small + l + 1, small + N + 1, small[l]); for ( int i = l + 1 ; i <= N; i++) { small[i] = small[l]; } // Variable to store the answer int res = 0 ; for ( int i = (k + X) / ( 1 + X); i <= k; i++) { if ( 1 * (i - 1 ) * (X + 1 ) + 1 <= N) { // Update res with maximum one res = Math.max( res, big[i] + small[N - 1 * (i - 1 ) * (X + 1 ) - 1 ]); } } // Return res return res; } // Driver Code public static void main(String[] args) { int arr[] = { 9 , 13 , 16 , 21 , 6 }; int X = 2 ; int K = 15 ; int N = arr.length; System.out.print(maxScore(arr, X, K, N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program, for the above approach maxn = int ( 1e5 ) # Utility function to calculate the # sum of elements as a prefix array def calc(arr, N) : arr.sort() arr[:: - 1 ] for i in range ( 1 , N + 1 ): arr[i] + = arr[i - 1 ] # Function to find the maximum score # that can be achieved by rearranging # the elements of given array def maxScore(arr, X, K, N) : # Arrays to store small and big elements small = [ 10 ] * (maxn + 5 ) big = [ 10 ] * (maxn + 5 ) k = 0 l = 0 # Iterate and segregate big and # small elements for i in range (N): if (arr[i] > K) : big[ + + k] = arr[i] else : small[ + + l] = arr[i] # If k = 0, return the sum # of small[] if (k = = 0 ) : sum = 0 for i in range ( 1 , N + 1 ): sum + = small[i] return sum # Prefix sums of small[] # and big[] calc(big, k) calc(small, l) # Initialize small[l] within the range for i in range (l + 1 , N + 1 ): small[i] = small[l] # Variable to store the answer res = 0 for i in range ((k + X) / ( 1 + X), k + 1 ): if ( 1 * (i - 1 ) * (X + 1 ) + 1 < = N) : # Update res with maximum one res = max ( res, big[i] + small[N - 1 * (i - 1 ) * (X + 1 ) - 1 ]) # Return res return res # Driver Code arr = [ 9 , 13 , 16 , 21 , 6 ] X = 2 K = 15 N = len (arr) print (maxScore(arr, X, K, N)) # This code is contributed by sanjoy_62. |
C#
// C# program, for the above approach using System; class GFG { static int maxn = ( int )1e5; // Utility function to calculate the // sum of elements as a prefix array static void calc( int [] arr, int N) { Array.Sort(arr); arr = reverse(arr); for ( int i = 1; i <= N; i++) { arr[i] += arr[i - 1]; } } static int [] reverse( int [] a) { int i, n = a.Length + 1, t; for (i = 1; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } return a; } // Function to find the maximum score // that can be achieved by rearranging // the elements of given array static int maxScore( int [] arr, int X, int K, int N) { // Arrays to store small and big elements int [] small = new int [maxn + 5]; int [] big = new int [maxn + 5]; int k = 0, l = 0; // Iterate and segregate big and // small elements for ( int i = 0; i < N; i++) { if (arr[i] > K) { big[++k] = arr[i]; } else { small[++l] = arr[i]; } } // If k = 0, return the sum // of small[] if (k == 0) { int sum = 0; for ( int i = 1; i <= N; i++) { sum += small[i]; } return sum; } // Prefix sums of small[] // and big[] calc(big, k); calc(small, l); // Initialize small[l] within the range // fill(small + l + 1, small + N + 1, small[l]); for ( int i = l + 1; i <= N; i++) { small[i] = small[l]; } // Variable to store the answer int res = 0; for ( int i = (k + X) / (1 + X); i <= k; i++) { if (1 * (i - 1) * (X + 1) + 1 <= N) { // Update res with maximum one res = Math.Max( res, big[i] + small[N - 1 * (i - 1) * (X + 1) - 1]); } } // Return res return res; } // Driver Code public static void Main( string [] args) { int [] arr = { 9, 13, 16, 21, 6 }; int X = 2; int K = 15; int N = arr.Length; Console.WriteLine(maxScore(arr, X, K, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach let maxn = 1e5; // Utility function to calculate the // sum of elements as a prefix array function calc(arr, N) { let arr1 = arr.slice(0, 1) let arr2 = arr.slice(1, N + 1) arr2.sort( function (a, b) { return a - b }); arr2.reverse(); arr = arr1.concat(arr2) for (let i = 1; i <= N; i++) { arr[i] += arr[i - 1]; } return arr; } // Function to find the maximum score // that can be achieved by rearranging // the elements of given array function maxScore(arr, X, K, N) { // Arrays to store small and big elements let small = new Array(maxn + 5).fill(0) let big = new Array(maxn + 5).fill(0); let k = 0, l = 0; // Iterate and segregate big and // small elements for (let i = 0; i < N; i++) { if (arr[i] > K) { big[++k] = arr[i]; } else { small[++l] = arr[i]; } } // If k = 0, return the sum // of small[] if (k == 0) { let sum = 0; for (let i = 1; i < N; i++) { sum += small[i]; } return sum; } // Prefix sums of small[] // and big[] big = calc(big, k); small = calc(small, l); // Initialize small[l] within the range for (let i = l + 1; i <= N; i++) { small[i] = small[l]; } // Variable to store the answer let res = 0; for (let i = Math.floor((k + X) / (1 + X)); i <= k; i++) { if (1 * (i - 1) * (X + 1) + 1 <= N) { // Update res with maximum one res = Math.max( res, big[i] + small[N - 1 * (i - 1) * (X + 1) - 1]); } } // Return res return res; } // Driver Code let arr = [9, 13, 16, 21, 6]; let X = 2; let K = 15; let N = arr.length; document.write(maxScore(arr, X, K, N)); // This code is contributed by Potta Lokesh </script> |
50
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Contact Us