Given an array arr of size N, the task is to maximize the sum of sum, of the remaining elements in the array, by removing the end elements.
Example:
Input: arr[] = {2, 3}
Output: 3
Explanation:
At first we will delete 2, then sum of remaining elements = 3. Then delete 3. Therefore sum of sum = 3 + 0 = 3.
We can also delete 3 first and then 2, but in this case, the sum of sum = 2 + 0 = 2
But since 3 is larger, therefore the output is 3.
Input: arr[] = {3, 1, 7, 2, 1}
Output: 39
Explanation:
At first we will delete 1 from last, then the sum of remaining elements
will be 13.
Then delete 2 from last, then the sum of remaining elements will be 11.
Then delete 3 from the beginning, then the sum of remaining elements will be 8.
Then we delete 1, the remaining sum is 7 and then delete 7.
Therefore the Sum of all remaining sums is 13 + 11 + 8 + 7 = 39, which is the maximum case.
Approach: The idea is to use Greedy Algorithm to solve this problem.
- First to calculate the total sum of the array.
- Then compare the elements on both ends and subtract the minimum value among the two, from the sum. This will make the remaining sum maximum.
- Then, add remaining sum to the result.
- Repeat the above steps till all the elements have been removed from the array. Then print the resultant sum.
Below is the implementation of the above approach:
C++
// C++ program to maximize the sum// of sum of the Array by// removing end elements#include <iostream>using namespace std;// Function to find// the maximum sum of sumint maxRemainingSum(int arr[], int n){ int sum = 0; // compute the sum of whole array for (int i = 0; i < n; i++) sum += arr[i]; int i = 0; int j = n - 1; int result = 0; // Traverse and remove the // minimum value from an end // to maximum the sum value while (i < j) { // If the left end element // is smaller than right end if (arr[i] < arr[j]) { // remove the left end element sum -= arr[i]; i++; } // If the right end element // is smaller than left end else { // remove the right end element sum -= arr[j]; j--; } // Add the remaining element // sum in the result result += sum; } // Return the maximum // sum of sum return result;}// Driver codeint main(){ int arr[] = { 3, 1, 7, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxRemainingSum(arr, N); return 0;} |
Java
// Java program to maximize the sum// of sum of the Array by removing// end elementsimport java.util.*;class GFG{ // Function to find// the maximum sum of sumstatic int maxRemainingSum(int arr[], int n){ int sum = 0; // Compute the sum of whole array for(int i = 0; i < n; i++) sum += arr[i]; int i = 0; int j = n - 1; int result = 0; // Traverse and remove the // minimum value from an end // to maximum the sum value while (i < j) { // If the left end element // is smaller than right end if (arr[i] < arr[j]) { // Remove the left end element sum -= arr[i]; i++; } // If the right end element // is smaller than left end else { // Remove the right end element sum -= arr[j]; j--; } // Add the remaining element // sum in the result result += sum; } // Return the maximum // sum of sum return result;}// Driver codepublic static void main(String args[]){ int arr[] = { 3, 1, 7, 2, 1 }; int N = arr.length; System.out.println(maxRemainingSum(arr, N));}}// This code is contributed by ankitkumar34 |
Python3
# Python3 program to maximize the # sum of sum of the Array by # removing end elements# Function to find the maximum# sum of sumdef maxRemainingSum(arr, n): sum = 0 # Compute the sum of whole array for i in range(n): sum += arr[i] i = 0 j = n - 1 result = 0 # Traverse and remove the # minimum value from an end # to maximum the sum value while (i < j): # If the left end element # is smaller than right end if (arr[i] < arr[j]): # Remove the left end element sum -= arr[i] i += 1 # If the right end element # is smaller than left end else: # Remove the right end element sum -= arr[j] j -= 1 # Add the remaining element # sum in the result result += sum; # Return the maximum # sum of sum return result# Driver codearr = [ 3, 1, 7, 2, 1 ]N = len(arr)print(maxRemainingSum(arr, N))# This code is contributed by ankitkumar34 |
C#
// C# program to maximize the sum// of sum of the Array by removing// end elementsusing System;class GFG{ // Function to find// the maximum sum of sumstatic int maxRemainingSum(int[] arr, int n){ int i, sum = 0; // Compute the sum of whole array for(i = 0; i < n; i++) sum += arr[i]; i = 0; int j = n - 1; int result = 0; // Traverse and remove the // minimum value from an end // to maximum the sum value while (i < j) { // If the left end element // is smaller than right end if (arr[i] < arr[j]) { // Remove the left end element sum -= arr[i]; i++; } // If the right end element // is smaller than left end else { // Remove the right end element sum -= arr[j]; j--; } // Add the remaining element // sum in the result result += sum; } // Return the maximum // sum of sum return result;}// Driver codepublic static void Main(){ int[] arr = { 3, 1, 7, 2, 1 }; int N = arr.Length; Console.Write(maxRemainingSum(arr, N));}}// This code is contributed by chitranayal |
Javascript
<script>// Javascript program to maximize the sum// of sum of the Array by// removing end elements// Function to find// the maximum sum of sumfunction maxRemainingSum(arr, n){ var sum = 0; // compute the sum of whole array for (var i = 0; i < n; i++) sum += arr[i]; var i = 0; var j = n - 1; var result = 0; // Traverse and remove the // minimum value from an end // to maximum the sum value while (i < j) { // If the left end element // is smaller than right end if (arr[i] < arr[j]) { // remove the left end element sum -= arr[i]; i++; } // If the right end element // is smaller than left end else { // remove the right end element sum -= arr[j]; j--; } // Add the remaining element // sum in the result result += sum; } // Return the maximum // sum of sum return result;}// Driver codevar arr = [ 3, 1, 7, 2, 1 ];var N = arr.length;document.write( maxRemainingSum(arr, N));</script> |
Output:
39
Time complexity: O(N), where N is the size of the given array.
Auxiliary space: O(1), as constant space is used.
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!
