Maximum pair sum in the given index ranges of an Array
Given an array arr containing N positive integers and the number of queries Q, for each query task is to find the maximum pair sum in the given index range [L, R] where L and R are the respective low and high indices.
Examples:
Input: arr = {3, 4, 5, 6, 7, 8}, Q[][2] = [[0, 3], [3, 5]]
Output:
11
15
Explanation:
For the first query, subarray is [3, 4, 5, 6]
All the pairs are (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)
Hence the maximum pair sum = (5 + 6) = 11
For the second query, subarray is [6, 7, 8]
All the pairs of the subarray are (6, 7), (6, 8), (7, 8)
Hence the maximum pair sum = (7 + 8) = 15
Naive Approach: For each query range, do the following
- Find the maximum and the second maximum in the given query range.
- Sum of maximum and second maximum will be the maximum pair sum of the given range.
Below is the implementation of the above approach:
C++
// C++ program to find maximum // pair sum in the given // index range of an Array #include <bits/stdc++.h> using namespace std; // Node structure to store a query struct node { int f; int s; }; // Function to find the required sum void findSum( int * arr, int n, int Q, node* query) { // Run a loop to iterate // over query array for ( int i = 0; i < Q; i++) { // declare first 'f' // and second 's' variables int f, s; // Initialise them with 0 f = s = 0; // Iterate over the // given array from // range query[i].f to query[i].s for ( int j = query[i].f; j <= query[i].s; j++) { // If the array element // value is greater than // current f, store // current f in s and // array element value in f if (arr[j] >= f) { s = f; f = arr[j]; } // else if element // is greater than s, // update s with // array element value else if (arr[j] > s) s = arr[j]; } // print the sum of f and s cout << (f + s) << endl; } } // Driver code int main() { // Given array and number of queries int arr[] = { 3, 4, 5, 6, 7, 8 }, Q = 2; int n = sizeof (arr) / sizeof (arr[0]); // Declare and define queries node query[Q]; query[0] = { 0, 3 }; query[1] = { 3, 5 }; findSum(arr, n, Q, query); } |
Java
// Java program to find maximum // pair sum in the given // index range of an Array class GFG{ // Node structure to store a query static class node { int f; int s; public node( int f, int s) { this .f = f; this .s = s; } }; // Function to find the required sum static void findSum( int []arr, int n, int Q, node []query) { // Run a loop to iterate // over query array for ( int i = 0 ; i < Q; i++) { // declare first 'f' // and second 's' variables int f, s; // Initialise them with 0 f = s = 0 ; // Iterate over the // given array from // range query[i].f to query[i].s for ( int j = query[i].f; j <= query[i].s; j++) { // If the array element // value is greater than // current f, store // current f in s and // array element value in f if (arr[j] >= f) { s = f; f = arr[j]; } // else if element // is greater than s, // update s with // array element value else if (arr[j] > s) s = arr[j]; } // print the sum of f and s System.out.print((f + s) + "\n" ); } } // Driver code public static void main(String[] args) { // Given array and number of queries int arr[] = { 3 , 4 , 5 , 6 , 7 , 8 }, Q = 2 ; int n = arr.length; // Declare and define queries node []query = new node[ 2 ]; query[ 0 ] = new node( 0 , 3 ); query[ 1 ] = new node( 3 , 5 ); findSum(arr, n, Q, query); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python program to find maximum # pair sum in the given # index range of an Array # Node structure to store a query from pickle import NONE class node: def __init__( self , f, s): self .f = f self .s = s # Function to find the required sum def findSum(arr, n, Q, query): # Run a loop to iterate # over query array for i in range (Q): # declare first 'f' # and second 's' variables # Initialise them with 0 f,s = 0 , 0 # Iterate over the # given array from # range query[i].f to query[i].s for j in range (query[i].f,query[i].s + 1 ): # If the array element # value is greater than # current f, store # current f in s and # array element value in f if (arr[j] > = f): s = f f = arr[j] # else if element # is greater than s, # update s with # array element value elif (arr[j] > s): s = arr[j] # print the sum of f and s print (f + s) # Driver code # Given array and number of queries arr = [ 3 , 4 , 5 , 6 , 7 , 8 ] Q = 2 n = len (arr) # Declare and define queries query = [ None ] * Q query[ 0 ] = node( 0 , 3 ) query[ 1 ] = node( 3 , 5 ) findSum(arr, n, Q, query) # This code is contributed by shinjanpatra |
C#
// C# program to find maximum // pair sum in the given // index range of an Array using System; class GFG{ // Node structure to store a query class node { public int f; public int s; public node( int f, int s) { this .f = f; this .s = s; } }; // Function to find the required sum static void findSum( int []arr, int n, int Q, node []query) { // Run a loop to iterate // over query array for ( int i = 0; i < Q; i++) { // declare first 'f' // and second 's' variables int f, s; // Initialise them with 0 f = s = 0; // Iterate over the // given array from // range query[i].f to query[i].s for ( int j = query[i].f; j <= query[i].s; j++) { // If the array element // value is greater than // current f, store // current f in s and // array element value in f if (arr[j] >= f) { s = f; f = arr[j]; } // else if element // is greater than s, // update s with // array element value else if (arr[j] > s) s = arr[j]; } // print the sum of f and s Console.Write((f + s) + "\n" ); } } // Driver code public static void Main(String[] args) { // Given array and number of queries int []arr = { 3, 4, 5, 6, 7, 8 }; int Q = 2; int n = arr.Length; // Declare and define queries node []query = new node[2]; query[0] = new node( 0, 3 ); query[1] = new node(3, 5 ); findSum(arr, n, Q, query); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to find maximum // pair sum in the given // index range of an Array // Node structure to store a query class node { constructor(f,s) { this .f = f; this .s = s; } } // Function to find the required sum function findSum(arr,n,Q,query) { // Run a loop to iterate // over query array for (let i = 0; i < Q; i++) { // declare first 'f' // and second 's' variables let f, s; // Initialise them with 0 f = s = 0; // Iterate over the // given array from // range query[i].f to query[i].s for (let j = query[i].f;j <= query[i].s;j++) { // If the array element // value is greater than // current f, store // current f in s and // array element value in f if (arr[j] >= f) { s = f; f = arr[j]; } // else if element // is greater than s, // update s with // array element value else if (arr[j] > s) s = arr[j]; } // print the sum of f and s document.write(f + s, "</br>" ); } } // Driver code // Given array and number of queries let arr = [ 3, 4, 5, 6, 7, 8 ], Q = 2; let n = arr.length; // Declare and define queries let query = new Array(Q); query[0] = new node( 0, 3 ); query[1] = new node( 3, 5 ); findSum(arr, n, Q, query); // This code is contributed by shinjanpatra </script> |
11 15
Performance Analysis:
- Time Complexity: In the above approach, we are looper over the array of length N for each of Q query. Thus the time complexity would be O(N*Q).
- Auxiliary Space: In the above approach there is no extra space used, therefore the Auxiliary Space complexity will be O(1).
Efficient Approach: The idea is to use the segment tree where each node of the segment tree store two values:
- Maximum of the given below subtree
- Second maximum of the given below subtree
- Time Complexity: In the above approach, we are building a segment tree which is of time complexity O(N) Then for each of Q queries, we find the solution in O(logN) time. So overall time complexity is O(N+Q*logN)
- Auxiliary Space Complexity: In the above approach, we are using extra space for storing the segment tree which is taking (4 * N + 1) space. So Auxiliary space complexity is O(N)
- Time Complexity: In the above approach, we are building a segment tree which is of time complexity O(N) Then for each of Q queries, we find the solution in O(logN) time. So overall time complexity is O(N+Q*logN)