Given an array arr[] of size N, the task is to find the maximum sum of the Array formed by replacing each element of the original array with the sum of adjacent elements.
Examples:
Input: arr = [4, 2, 1, 3]
Output: 23
Explanation:
Replacing each element of the original array with the sum of adjacent elements:
4 + 2 = 6
6 + 1 = 7
7 + 3 = 10
Array formed by replacing each element of the original array with the sum of adjacent elements: [6, 7, 10]
Therefore, Sum = 6 + 7 + 10 = 23
Input: arr = [2, 3, 9, 8, 4]
Output: 88
Explanation:
Replacing each element of the original array with the sum of adjacent elements to get maximum sum:
9 + 8 = 17
17 + 4 = 21
21 + 3 = 24
24 + 2 = 26
Array formed by replacing each element of the original array with the sum of adjacent elements: [17, 21, 24, 26]
Therefore, Sum = 17 + 21 + 24 + 26 = 88.
Approach:
- Scan through the array to pick the adjacent pair with the highest sum.
- From there on, using Greedy algorithm, pick the left or right integer, whichever is greater.
- Repeat the process till only a single element is left in the array.
Below is the implementation of the above approach:
C++
// C++ program to find the maximum sum // of Array formed by replacing each // element with sum of adjacent elements #include <bits/stdc++.h> using namespace std; // Function to calculate the possible // maximum cost of the array int getTotalTime(vector< int >& arr) { // Check if array size is 0 if (arr.size() == 0) return 0; // Initialise left and right variables int l = -1, r = -1; for ( int i = 1; i < arr.size(); i++) { if (l == -1 || (arr[i - 1] + arr[i]) > (arr[l] + arr[r])) { l = i - 1; r = i; } } // Calculate the current cost int currCost = arr[l] + arr[r]; int totalCost = currCost; l--; r++; // Iterate until left variable reaches 0 // and right variable is less than array size while (l >= 0 || r < arr.size()) { int left = l < 0 ? INT_MIN : arr[l]; int right = r >= arr.size() ? INT_MIN : arr[r]; // Check if left integer is greater // than the right then add left integer // to the current cost and // decrement the left variable if (left > right) { currCost += left; totalCost += currCost; l--; } // Executes if right integer is // greater than left then add // right integer to the current cost // and increment the right variable else { currCost += right; totalCost += currCost; r++; } } // Return the final answer return totalCost; } // Driver code int main( int argc, char * argv[]) { vector< int > arr = { 2, 3, 9, 8, 4 }; cout << getTotalTime(arr) << endl; return 0; } |
Java
// Java program to find the maximum sum // of array formed by replacing each // element with sum of adjacent elements class GFG{ // Function to calculate the possible // maximum cost of the array static int getTotalTime( int []arr) { // Check if array size is 0 if (arr.length == 0 ) return 0 ; // Initialise left and right variables int l = - 1 , r = - 1 ; for ( int i = 1 ; i < arr.length; i++) { if (l == - 1 || (arr[i - 1 ] + arr[i]) > (arr[l] + arr[r])) { l = i - 1 ; r = i; } } // Calculate the current cost int currCost = arr[l] + arr[r]; int totalCost = currCost; l--; r++; // Iterate until left variable reaches 0 // and right variable is less than array size while (l >= 0 || r < arr.length) { int left = (l < 0 ? Integer.MIN_VALUE : arr[l]); int right = (r >= arr.length ? Integer.MIN_VALUE : arr[r]); // Check if left integer is greater // than the right then add left integer // to the current cost and // decrement the left variable if (left > right) { currCost += left; totalCost += currCost; l--; } // Executes if right integer is // greater than left then add // right integer to the current cost // and increment the right variable else { currCost += right; totalCost += currCost; r++; } } // Return the final answer return totalCost; } // Driver code public static void main(String[] args) { int []arr = { 2 , 3 , 9 , 8 , 4 }; System.out.print(getTotalTime(arr) + "\n" ); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find the maximum sum # of Array formed by replacing each # element with sum of adjacent elements import sys # Function to calculate the possible # maximum cost of the array def getTotalTime(arr): # Check if array size is 0 if ( len (arr) = = 0 ): return 0 # Initialise left and right variables l = - 1 r = - 1 for i in range ( 1 , len (arr), 1 ): if (l = = - 1 or (arr[i - 1 ] + arr[i]) > (arr[l] + arr[r])): l = i - 1 r = i # Calculate the current cost currCost = arr[l] + arr[r] totalCost = currCost l - = 1 r + = 1 # Iterate until left variable reaches 0 # and right variable is less than array size while (l > = 0 or r < len (arr)): if (l < 0 ): left = sys.maxsize else : left = arr[l] if (r > = len (arr)): right = - sys.maxsize - 1 else : right = arr[r] # Check if left integer is greater # than the right then add left integer # to the current cost and # decrement the left variable if (left > right): currCost + = left totalCost + = currCost l - = 1 # Executes if right integer is # greater than left then add # right integer to the current cost # and increment the right variable else : currCost + = right totalCost + = currCost r + = 1 # Return the final answer return totalCost # Driver code if __name__ = = '__main__' : arr = [ 2 , 3 , 9 , 8 , 4 ] print (getTotalTime(arr)) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find the maximum sum // of array formed by replacing each // element with sum of adjacent elements using System; class GFG{ // Function to calculate the possible // maximum cost of the array static int getTotalTime( int []arr) { // Check if array size is 0 if (arr.Length == 0) return 0; // Initialise left and right variables int l = -1, r = -1; for ( int i = 1; i < arr.Length; i++) { if (l == -1 || (arr[i - 1] + arr[i]) > (arr[l] + arr[r])) { l = i - 1; r = i; } } // Calculate the current cost int currCost = arr[l] + arr[r]; int totalCost = currCost; l--; r++; // Iterate until left variable reaches 0 // and right variable is less than array size while (l >= 0 || r < arr.Length) { int left = (l < 0 ? int .MinValue : arr[l]); int right = (r >= arr.Length ? int .MinValue : arr[r]); // Check if left integer is greater // than the right then add left integer // to the current cost and // decrement the left variable if (left > right) { currCost += left; totalCost += currCost; l--; } // Executes if right integer is // greater than left then add // right integer to the current cost // and increment the right variable else { currCost += right; totalCost += currCost; r++; } } // Return the readonly answer return totalCost; } // Driver code public static void Main(String[] args) { int []arr = { 2, 3, 9, 8, 4 }; Console.Write(getTotalTime(arr) + "\n" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to find the maximum sum // of Array formed by replacing each // element with sum of adjacent elements // Function to calculate the possible // maximum cost of the array function getTotalTime(arr) { // Check if array size is 0 if (arr.length == 0) return 0; // Initialise left and right variables var l = -1, r = -1; for ( var i = 1; i < arr.length; i++) { if (l == -1 || (arr[i - 1] + arr[i]) > (arr[l] + arr[r])) { l = i - 1; r = i; } } // Calculate the current cost var currCost = arr[l] + arr[r]; var totalCost = currCost; l--; r++; // Iterate until left variable reaches 0 // and right variable is less than array size while (l >= 0 || r < arr.length) { var left = l < 0 ? -1000000000 : arr[l]; var right = r >= arr.length ? -1000000000 : arr[r]; // Check if left integer is greater // than the right then add left integer // to the current cost and // decrement the left variable if (left > right) { currCost += left; totalCost += currCost; l--; } // Executes if right integer is // greater than left then add // right integer to the current cost // and increment the right variable else { currCost += right; totalCost += currCost; r++; } } // Return the final answer return totalCost; } // Driver code var arr = [2, 3, 9, 8, 4]; document.write( getTotalTime(arr)); // This code is contributed by noob2000. </script> |
88
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!