Maximum sum of Array formed by replacing each element with sum of adjacent elements

0 0 7 minutes read

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>

Output:

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 zambiatek!