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 arrayint 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 codeint 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 elementsclass GFG{// Function to calculate the possible// maximum cost of the arraystatic 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 codepublic 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 elementsimport sys# Function to calculate the possible# maximum cost of the arraydef 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 codeif __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 elementsusing System;class GFG{ // Function to calculate the possible// maximum cost of the arraystatic 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 codepublic 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 arrayfunction 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 codevar arr = [2, 3, 9, 8, 4];document.write( getTotalTime(arr));// This code is contributed by noob2000.</script> |
Output:
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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
