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 sumint 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 codeint 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 elementsimport java.util.*;class GFG{// Function for maximising the sumstatic 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 codepublic 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 sumdef 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 codeN = 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 elementsusing System;class GFG{// Function for maximising the sumstatic 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 codepublic 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 sumfunction 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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
