Given an array arr[] containing N integers, the task is to find the maximum sum obtained by adding the elements at the same index of the original array and of the reversed array.
Example:
Input: arr[]={ 1, 8, 9, 5, 4, 6 }
Output: 14
Explanation:
Original array : {1, 8, 9, 5, 4, 6}
Reversed array: {6, 4, 5, 9, 8, 1}
Adding corresponding indexes element:
{1+6=7, 8+4=12, 9+5=14, 5+9=14, 4+8=12, 6+1=7}
So, The Maximum sum is 14.Input: arr[]={-31, 5, -1, 7, -5}
Output: 12
Naive approach: Create a reversed array and return the maximum sum after adding corresponding index elements.
Maximum sum after adding the corresponding reversed array element
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arrayint maximumSum(int arr[], int n){ int c = 0; // Creating reversed array int reversed[n]; for (int i = n - 1; i >= 0; i--) reversed = arr[i]; int res = INT_MIN; // Adding corresponding // indexes of original // and reversed array for (int i = 0; i < n; i++) { res = std::max(res, arr[i] + reversed[i]); } return res;}// Driver Codeint main(){ int arr[] = { 1, 8, 9, 5, 4, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, n); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to find the maximum // sum obtained by adding the // elements at the same index of // the original array and of // the reversed array static int maximumSum(int[] arr, int n) { int c = 0; // Creating reversed array int[] reversed = new int[n]; for (int i = n - 1; i >= 0; i--) reversed = arr[i]; int res = Integer.MIN_VALUE; // Adding corresponding // indexes of original // and reversed array for (int i = 0; i < n; i++) { res = Math.max(res, arr[i] + reversed[i]); } return res; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 8, 9, 5, 4, 6 }; int n = arr.length; System.out.println(maximumSum(arr, n)); }}// This code is contributed by maddler. |
Python3
# Python 3 program for the above approachimport sys# Function to find the maximum# sum obtained by adding the# elements at the same index of# the original array and of# the reversed arraydef maximumSum(arr, n): c = 0 # Creating reversed array reversed = [0]*n for i in range(n - 1, -1, -1): reversed = arr[i] c += 1 res = -sys.maxsize - 1 # Adding corresponding # indexes of original # and reversed array for i in range(n): res = max(res, arr[i] + reversed[i]) return res# Driver Codeif __name__ == "__main__": arr = [1, 8, 9, 5, 4, 6] n = len(arr) print(maximumSum(arr, n)) # This code is contributed by ukasp. |
C#
/*package whatever //do not write package name here */using System;public class GFG { // Function to find the maximum // sum obtained by adding the // elements at the same index of // the original array and of // the reversed array static int maximumSum(int[] arr, int n) { int c = 0; // Creating reversed array int[] reversed = new int[n]; for (int i = n - 1; i >= 0; i--) reversed = arr[i]; int res = int.MinValue; // Adding corresponding // indexes of original // and reversed array for (int i = 0; i < n; i++) { res = Math.Max(res, arr[i] + reversed[i]); } return res; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 8, 9, 5, 4, 6 }; int n = arr.Length; Console.WriteLine(maximumSum(arr, n)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arrayfunction maximumSum(arr, n) { let c = 0; // Creating reversed array let reversed = new Array(n); for (let i = n - 1; i >= 0; i--) reversed = arr[i]; let res = Number.MIN_SAFE_INTEGER; // Adding corresponding // indexes of original // and reversed array for (let i = 0; i < n; i++) { res = Math.max(res, arr[i] + reversed[i]); } return res;}// Driver Codelet arr = [1, 8, 9, 5, 4, 6];let n = arr.length;document.write(maximumSum(arr, n));// This code is contributed by saurabh_jaiswal.</script> |
Output:
14
Time Complexity: O(N)
Auxiliary Space: O(N)
Effective Approach: This problem can be solved using the two-pointer algorithm. So follow the below steps to find the answer:
- Create a front pointer that will point to the first element in the array and a rear pointer that will point to the last element.
- Now run a loop until these two pointers cross each other. In each iteration:
- Add the elements to which front and rear pointers are pointing. This is the sum of the corresponding elements in the original and the reversed array.
- Increase the front pointer by 1 and decrease the rear pointer by 1.
- After the loop ends, return the maximum sum obtained.
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arrayint maximumSum(int arr[], int n){ // Creating i as front pointer // and j as rear pointer int i = 0, j = n - 1; int max = INT_MIN; while (i <= j) { if (max < arr[i] + arr[j]) max = arr[i] + arr[j]; i++; j--; } // Returning the maximum value return max;}// Driver Codeint main(){ int arr[] = { 1, 8, 9, 5, 4, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG {// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arraystatic int maximumSum(int []arr, int n){ // Creating i as front pointer // and j as rear pointer int i = 0, j = n - 1; int max = Integer.MIN_VALUE; while (i <= j) { if (max < arr[i] + arr[j]) max = arr[i] + arr[j]; i++; j--; } // Returning the maximum value return max;}// Driver Codepublic static void main(String args[]){ int []arr = { 1, 8, 9, 5, 4, 6 }; int n = arr.length; System.out.println(maximumSum(arr, n));}}// This code is contributed by Samim Hossain Mondal. |
Python3
# python program for the above approachINT_MIN = -2147483647 - 1# Function to find the maximum# sum obtained by adding the# elements at the same index of# the original array and of# the reversed arraydef maximumSum(arr, n): # Creating i as front pointer # and j as rear pointer i = 0 j = n - 1 max = INT_MIN while (i <= j): if (max < arr[i] + arr[j]): max = arr[i] + arr[j] i += 1 j -= 1 # Returning the maximum value return max# Driver Codeif __name__ == "__main__": arr = [1, 8, 9, 5, 4, 6] n = len(arr) print(maximumSum(arr, n)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arraystatic int maximumSum(int []arr, int n){ // Creating i as front pointer // and j as rear pointer int i = 0, j = n - 1; int max = Int32.MinValue; while (i <= j) { if (max < arr[i] + arr[j]) max = arr[i] + arr[j]; i++; j--; } // Returning the maximum value return max;}// Driver Codepublic static void Main(){ int []arr = { 1, 8, 9, 5, 4, 6 }; int n = arr.Length; Console.Write(maximumSum(arr, n));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum// sum obtained by adding the// elements at the same index of// the original array and of// the reversed arrayfunction maximumSum(arr, n){ // Creating i as front pointer // and j as rear pointer let i = 0, j = n - 1; let max = Number.MIN_SAFE_INTEGER; while (i <= j) { if (max < arr[i] + arr[j]) max = arr[i] + arr[j]; i++; j--; } // Returning the maximum value return max;}// Driver Codelet arr = [ 1, 8, 9, 5, 4, 6 ];let n = arr.length;document.write(maximumSum(arr, n));// This code is contributed by Samim Hossain Mondal.</script> |
Output:
14
Time Complexity: O(N)
Auxiliary Space: O(1).
