Given an array arr[] of size N, the task is to find the maximum possible sum of the array elements such that the element can be chosen as per the below conditions:
- For each index i the value of the element is arr[i], then we can add any element from 1 to min(N, arr[i]) into the sum or else leave that element.
- If some element is already added to the sum, then we can not add the same element again to the sum.
Examples:
Input: arr[] = {1, 2, 2, 4}
Output: 7
Explanation:
Initially, the total sum is 0.
Sum after adding element at index 1 to sum = 1. Elements added to sum = {1}
Sum after adding element at index 2 to sum = 3. Elements added to sum = {1, 2}
Now, coming at index 3 we can not add any element from (1 to 2) to the sum because we have already added the elements {1, 2} into the sum. So, leave the element at index 3.
Then add the element at index 4 to sum since 4 was not added to sum before therefore the maximum sum we can get is 3+4=7.Input: arr[] = {4, 4, 1, 5}
Output: 13
Approach: This problem can be solved using Greedy Technique. Below are the steps:
- Sort the elements of the array in ascending order.
- Maintain the maximum possible number (say maxPossible) which can be added to the total sum.
- Initialise maxPossible with the maximum element of the array and add it to the total sum.
- Traverse the array from the end to the beginning and check if the given element value has been added to the total sum before or not.
- If the element value has been added before then we will add (element – 1) to the total sum and if the element value is less than maxPossible then we will add that number and change the maxPossible to the element value.
- Print the value of total sum after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;// Function that finds the maximum sum// of the array elements according to// the given conditionll findMaxValue(int arr[], int n){ // Sort the array sort(arr, arr + n); // Take the max value from the array ll ans = arr[n - 1]; ll maxPossible = arr[n - 1]; // Iterate from the end of the array for (int i = n - 2; i >= 0; --i) { if (maxPossible > 0) { // Check for the number had // come before or not if (arr[i] >= maxPossible) { // Take the value which is // not occurred already ans += (maxPossible - 1); maxPossible = maxPossible - 1; } else { // Change max to new value maxPossible = arr[i]; ans += maxPossible; } } } // Return the maximum sum return ans;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 4, 4, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << findMaxValue(arr, n);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that finds the maximum sum// of the array elements according to// the given conditionstatic int findMaxValue(int arr[], int n){ // Sort the array Arrays.sort(arr); // Take the max value from the array int ans = arr[n - 1]; int maxPossible = arr[n - 1]; // Iterate from the end of the array for (int i = n - 2; i >= 0; --i) { if (maxPossible > 0) { // Check for the number had // come before or not if (arr[i] >= maxPossible) { // Take the value which is // not occurred already ans += (maxPossible - 1); maxPossible = maxPossible - 1; } else { // Change max to new value maxPossible = arr[i]; ans += maxPossible; } } } // Return the maximum sum return ans;}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 4, 4, 1, 5 }; int n = arr.length; // Function Call System.out.print(findMaxValue(arr, n));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program for the above approach# Function that finds the maximum sum# of the array elements according to# the given conditiondef findMaxValue(arr, n): # Sort the array arr.sort() # Take the max value from the array ans = arr[n - 1] maxPossible = arr[n - 1] # Iterate from the end of the array for i in range(n - 2, -1, -1): if (maxPossible > 0): # Check for the number had # come before or not if (arr[i] >= maxPossible): # Take the value which is # not occurred already ans += (maxPossible - 1) maxPossible = maxPossible - 1 else: # Change max to new value maxPossible = arr[i] ans += maxPossible # Return the maximum sum return ans# Driver codeif __name__=='__main__': # Given array arr[] arr = [ 4, 4, 1, 5 ] n = len(arr) # Function call print(findMaxValue(arr,n))# This code is contributed by rutvik_56 |
C#
// C# program for the above approachusing System;class GFG{// Function that finds the maximum sum// of the array elements according to// the given conditionstatic int findMaxValue(int []arr, int n){ // Sort the array Array.Sort(arr); // Take the max value from the array int ans = arr[n - 1]; int maxPossible = arr[n - 1]; // Iterate from the end of the array for (int i = n - 2; i >= 0; --i) { if (maxPossible > 0) { // Check for the number had // come before or not if (arr[i] >= maxPossible) { // Take the value which is // not occurred already ans += (maxPossible - 1); maxPossible = maxPossible - 1; } else { // Change max to new value maxPossible = arr[i]; ans += maxPossible; } } } // Return the maximum sum return ans;}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 4, 4, 1, 5 }; int n = arr.Length; // Function Call Console.Write(findMaxValue(arr, n));}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// JavaScript program for the above approach // Function that finds the maximum sum // of the array elements according to // the given condition function findMaxValue(arr, n) { // Sort the array arr.sort((a, b) => a - b); // Take the max value from the array let ans = arr[n - 1]; let maxPossible = arr[n - 1]; // Iterate from the end of the array for (let i = n - 2; i >= 0; --i) { if (maxPossible > 0) { // Check for the number had // come before or not if (arr[i] >= maxPossible) { // Take the value which is // not occurred already ans += (maxPossible - 1); maxPossible = maxPossible - 1; } else { // Change max to new value maxPossible = arr[i]; ans += maxPossible; } } } // Return the maximum sum return ans; } // Driver Code // Given array arr[] let arr = [ 4, 4, 1, 5 ]; let n = arr.length; // Function Call document.write(findMaxValue(arr, n)); // This code is contributed by Surbhi Tyagi.</script> |
Output:
13
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
