Maximize the sum of differences of consecutive elements after removing exactly K elements
Given a sorted array arr[] of length N and an integer K such that K < N, the task is to remove exactly K elements from the array such that the sum of the differences of the consecutive elements of the array is maximized.
Examples:
Input: arr[] = {1, 2, 3, 4}, K = 1
Output: 3
Let’s consider all the possible cases:
a) Remove arr[0]: arr[] = {2, 3, 4}, ans = 2
b) Remove arr[1]: arr[] = {1, 3, 4}, ans = 3
c) Remove arr[2]: arr[] = {1, 2, 4}, ans = 3
d) Remove arr[3]: arr[] = {1, 2, 3}, ans = 2
3 is the maximum of all the answers.
Input: arr[] = {1, 2, 10}, K = 2
Output: 0
Approach: There are two cases:
- If K < N – 1 then the answer will be arr[N – 1] – arr[0]. This is because any K elements from the N – 2 internal elements of the array can be deleted without affecting the maximized sum of differences. For example, if any single element has to be removed from 1, 2, 3 and 4 then no matter whether 2 is removed or 3 is removed the final sum of difference will remain the same i.e. ((3 – 1) + (4 – 3)) = 3 which is equal to ((2 – 1) + (4 – 2)) = 3.
- If K = N – 1 then the answer will be 0 because only a single element remains that is both the minimum and the maximum. Thus, the answer is 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximized sum int findSum( int * arr, int n, int k) { // Remove any k internal elements if (k <= n - 2) return (arr[n - 1] - arr[0]); return 0; } // Driver code int main() { int arr[] = { 1, 2, 3, 4 }; int n = sizeof (arr) / sizeof ( int ); int k = 1; cout << findSum(arr, n, k); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the maximized sum static int findSum( int []arr, int n, int k) { // Remove any k internal elements if (k <= n - 2 ) return (arr[n - 1 ] - arr[ 0 ]); return 0 ; } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 4 }; int n = arr.length; int k = 1 ; System.out.println(findSum(arr, n, k)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the maximized sum def findSum(arr, n, k) : # Remove any k internal elements if (k < = n - 2 ) : return (arr[n - 1 ] - arr[ 0 ]); return 0 ; # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 ]; n = len (arr); k = 1 ; print (findSum(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximized sum static int findSum( int []arr, int n, int k) { // Remove any k internal elements if (k <= n - 2) return (arr[n - 1] - arr[0]); return 0; } // Driver code public static void Main () { int []arr = { 1, 2, 3, 4 }; int n = arr.Length; int k = 1; Console.WriteLine(findSum(arr, n, k)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximized sum function findSum(arr, n, k) { // Remove any k internal elements if (k <= n - 2) return (arr[n - 1] - arr[0]); return 0; } // Driver code var arr = [1, 2, 3, 4]; var n = arr.length; var k = 1; document.write( findSum(arr, n, k)); </script> |
Output:
3
Time Complexity: O(1)
Auxiliary Space: O(1)