Maximize sum of absolute difference between adjacent elements in Array with sum K
Given two integers N and K, the task is to maximize the sum of absolute differences between adjacent elements of an array of length N and sum K.
Examples:
Input: N = 5, K = 10
Output: 20
Explanation:
The array arr[] with sum 10 can be {0, 5, 0, 5, 0}, maximizing the sum of absolute difference of adjacent elements ( 5 + 5 + 5 + 5 = 20)Input: N = 2, K = 10
Output: 10
Approach:
To maximize the sum of adjacent elements, follow the steps below:
- If N is 2, the maximum sum possible is K by placing K in 1 index and 0 on the other.
- If N is 1, the maximum sum possible will always be 0.
- For all other values of N, the answer will be 2 * K.
Illustration:
For N = 3, the arrangement {0, K, 0} maximizes the sum of absolute difference between adjacent elements to 2 * K.
For N = 4, the arrangement {0, K/2, 0, K/2} or {0, K, 0, 0} maximizes the required sum of absolute difference between adjacent elements to 2 * K.
Below is the implementation of the above approach:
C++
// C++ program to maximize the // sum of absolute differences // between adjacent elements #include <bits/stdc++.h> using namespace std; // Function for maximizing the sum int maxAdjacentDifference( int N, int K) { // Difference is 0 when only // one element is present // in array if (N == 1) { return 0; } // Difference is K when // two elements are // present in array if (N == 2) { return K; } // Otherwise return 2 * K; } // Driver code int main() { int N = 6; int K = 11; cout << maxAdjacentDifference(N, K); return 0; } |
Java
// Java program to maximize the // sum of absolute differences // between adjacent elements import java.util.*; class GFG{ // Function for maximising the sum static int maxAdjacentDifference( int N, int K) { // Difference is 0 when only // one element is present // in array if (N == 1 ) { return 0 ; } // Difference is K when // two elements are // present in array if (N == 2 ) { return K; } // Otherwise return 2 * K; } // Driver code public static void main(String[] args) { int N = 6 ; int K = 11 ; System.out.print(maxAdjacentDifference(N, K)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to maximize the # sum of absolute differences # between adjacent elements # Function for maximising the sum def maxAdjacentDifference(N, K): # Difference is 0 when only # one element is present # in array if (N = = 1 ): return 0 ; # Difference is K when # two elements are # present in array if (N = = 2 ): return K; # Otherwise return 2 * K; # Driver code N = 6 ; K = 11 ; print (maxAdjacentDifference(N, K)); # This code is contributed by Code_Mech |
C#
// C# program to maximize the // sum of absolute differences // between adjacent elements using System; class GFG{ // Function for maximising the sum static int maxAdjacentDifference( int N, int K) { // Difference is 0 when only // one element is present // in array if (N == 1) { return 0; } // Difference is K when // two elements are // present in array if (N == 2) { return K; } // Otherwise return 2 * K; } // Driver code public static void Main(String[] args) { int N = 6; int K = 11; Console.Write(maxAdjacentDifference(N, K)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to maximize the // sum of absolute differences // between adjacent elements // Function for maximising the sum function maxAdjacentDifference(N, K) { // Difference is 0 when only // one element is present // in array if (N == 1) { return 0; } // Difference is K when // two elements are // present in array if (N == 2) { return K; } // Otherwise return 2 * K; } // Driver Code let N = 6; let K = 11; document.write(maxAdjacentDifference(N, K)); // This code is contributed by susmitakundugoaldanga. </script> |
22
Time Complexity: O(1).
Auxiliary Space: O(1)