Maximum value of |arr[0] – arr[1]| + |arr[1] – arr[2]| + … +|arr[n – 2] – arr[n – 1]| when elements are from 1 to n
Given an array arr[] of size n whose elements are from the range [1, n]. The task is to find maximum value of |arr[0] – arr[1]| + |arr[1] – arr[2]| + … +|arr[n – 2] – arr[n – 1]|. You can arrange the numbers in the array in any order.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 7
Arrange the array in this way for max value, arr[] = {3, 1, 4, 2}
|3 – 1| + |1 – 4| + |4 – 2| = 2 + 3 + 2 = 7Input: arr[] = {1, 2, 3}
Output: 3
We arrange the array as {2, 1, 3}
A Simple Approach is to generate all possible permutations. Compute the value for every permutation and find the maximum value.
Efficient Approach:
The maximum sum with one element is 0.
The maximum sum with two elements is 1
The maximum sum with three elements is 3 (explained above)
The maximum sum with four elements is 7 (explained above)
It can be observed that for different values of n, a pattern for the maximum sum of absolute differences is 0, 1, 3, 7, 11, 17, 23, 31, 39, 49, ….. whose nth term is ((n * n / 2) – 1).
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 maximum // required value int maxValue( int n) { if (n == 1) return 0; return ((n * n / 2) - 1); } // Driver code int main() { int n = 4; cout << maxValue(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the maximum // required value static int maxValue( int n) { if (n == 1 ) return 0 ; return ((n * n / 2 ) - 1 ); } // Driver code public static void main(String args[]) { int n = 4 ; System.out.print(maxValue(n)); } } |
Python
# Python3 implementation of the approach # Function to return the maximum # required value def maxValue(n): if (n = = 1 ): return 0 return (( n * n / / 2 ) - 1 ) # Driver code n = 4 print (maxValue(n)) |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum // required value static int maxValue( int n) { if (n == 1) return 0; return ((n * n / 2) - 1); } // Driver code public static void Main() { int n = 4; Console.WriteLine(maxValue(n)); } } |
PHP
<?php // Function to return the maximum // required value function maxValue( $n ) { if ( $n == 1) return 0; return (( $n * $n / 2) - 1); } // Driver code $n = 4; echo maxValue( $n ); ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum // required value function maxValue(n) { if (n == 1) return 0; return (parseInt(n * n / 2) - 1); } // Driver code var n = 4; document.write(maxValue(n)); // This code is contributed by noob2000. </script> |
7
Time Complexity: O(1)
Auxiliary Space: O(1)