Given an array, find maximum sum of smallest and second smallest elements chosen from all possible sub-arrays. More formally, if we write all (nC2) sub-arrays of array of size >=2 and find the sum of smallest and second smallest, then our answer will be maximum sum among them.
 
Example 1:
Input : arr[] = [4, 3, 1, 5, 6]
Output : 11
Subarrays with smallest and 
second smallest are,
[4, 3]        
smallest = 3    second smallest = 4
[4, 3, 1]    
smallest = 1    second smallest = 3
[4, 3, 1, 5]    
smallest = 1    second smallest = 3
[4, 3, 1, 5, 6]    
smallest = 1    second smallest = 3
[3, 1]         
smallest = 1    second smallest = 3
[3, 1, 5]     
smallest = 1    second smallest = 3
[3, 1, 5, 6]    
smallest = 1    second smallest = 3
[1, 5]        
smallest = 1    second smallest = 5
[1, 5, 6]    
smallest = 1    second smallest = 5
[5, 6]         
smallest = 5    second smallest = 6
Maximum sum among all 
above choices is, 5 + 6 = 11
 
Example 2:
Input : arr[] = {5, 4, 3, 1, 6} 
Output : 9
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function pairWithMaxSum() which takes the array Arr[] and its size N as inputs and returns the maximum sum of smallest and second smallest elements chosen from all possible subarrays.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
2 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def pairWithMaxSum(self, arr, N):
        # Your code goes here
    


Solutions:
class Solution:

	def pairWithMaxSum(self, arr, N):
		st = []
		ans = []
		st.append(arr[0])
		for i in arr[1:]:
			b = st.pop()
			c = b + i
			ans.append(c)
			st.append(i)
		return max(ans)


class Solution:

	def pairWithMaxSum(self, arr, N):
		z = []
		l = 0
		for i in range(N):
			if z:
				if z[-1] + arr[i] > l:
					l = z[-1] + arr[i]
				z.pop()
			z.append(arr[i])
		return l


class Solution:

	def pairWithMaxSum(self, arr, N):
		z = []
		for i in range(N - 1):
			z.append(sum(arr[i:i + 2]))
		return max(z)


class Solution:

	def pairWithMaxSum(self, arr, N):
		sum = 0
		for i in range(N - 1):
			maxi = max(sum, arr[i] + arr[i + 1])
			sum = maxi
		return maxi


class Solution:

	def pairWithMaxSum(self, arr, N):
		if N < 2:
			return -1
		res = arr[0] + arr[1]
		for i in range(1, N - 1):
			res = max(res, arr[i] + arr[i + 1])
		return res


class Solution:

	def pairWithMaxSum(self, arr, N):
		if N == 1:
			return arr[0]
		max = 0
		for i in range(1, N):
			temp = arr[i] + arr[i - 1]
			if temp > max:
				max = temp
		return max


class Solution:

	def pairWithMaxSum(self, arr, N):
		max_sum = 0
		for n in range(N - 1):
			if max_sum < arr[n] + arr[n + 1]:
				max_sum = arr[n] + arr[n + 1]
		return max_sum


class Solution:

	def pairWithMaxSum(self, arr, N):
		m = 0
		for i in range(N - 1):
			if m < arr[i] + arr[i + 1]:
				m = arr[i] + arr[i + 1]
		return m


class Solution:

	def pairWithMaxSum(self, arr, N):
		import sys
		maxi = -sys.maxsize
		for i in range(1, N):
			curr = arr[i] + arr[i - 1]
			maxi = max(curr, maxi)
		return maxi


class Solution:

	def pairWithMaxSum(self, arr, N):
		ans = float('-inf')
		i = 0
		j = 1
		while j < N:
			ans = max(ans, arr[i] + arr[j])
			i += 1
			j += 1
		return ans


class Solution:

	def pairWithMaxSum(self, arr, N):
		i = 0
		j = 1
		sumi = 0
		while j < N:
			sumi = max(sumi, arr[i] + arr[j])
			i += 1
			j += 1
		return sumi


class Solution:

	def pairWithMaxSum(self, arr, N):
		res = -1
		for i in range(N - 1):
			s = arr[i] + arr[i + 1]
			res = max(res, s)
		return res


class Solution:

	def pairWithMaxSum(self, arr, N):
		sum = 0
		maxm = 0
		for i in range(1, N):
			sum = arr[i - 1] + arr[i]
			if sum > maxm:
				maxm = sum
		return maxm


class Solution:

	def pairWithMaxSum(self, arr, N):
		ans = arr[0] + arr[1]
		summ = ans
		for i in range(2, N):
			summ += arr[i] - arr[i - 2]
			ans = max(ans, summ)
		return ans


class Solution:

	def pairWithMaxSum(self, arr, N):
		result = 0
		for i in range(N - 1):
			res = arr[i] + arr[i + 1]
			result = max(result, res)
		return result


class Solution:

	def pairWithMaxSum(self, arr, N):
		m = float('-inf')
		for i in range(N - 1):
			if arr[i] + arr[i + 1] >= m:
				m = arr[i] + arr[i + 1]
		return m


class Solution:

	def pairWithMaxSum(self, arr, N):
		s = 0
		for i in range(1, N):
			t = arr[i] + arr[i - 1]
			s = max(s, t)
		return s


class Solution:

	def pairWithMaxSum(self, arr, N):
		cs = ms = 0
		for i in range(len(arr) - 1):
			cs = arr[i] + arr[i + 1]
			ms = max(cs, ms)
		return ms


class Solution:

	def pairWithMaxSum(self, arr, N):
		r = arr[0] + arr[1]
		for i in range(1, N - 1):
			r = max(r, arr[i] + arr[i + 1])
		return r


class Solution:

	def pairWithMaxSum(self, arr, N):
		max_sum = -1
		for i in range(N - 1):
			if arr[i] + arr[i + 1] > max_sum:
				max_sum = arr[i] + arr[i + 1]
		return max_sum


class Solution:

	def pairWithMaxSum(self, arr, n):
		a = []
		for i in range(n - 1):
			a.append(arr[i] + arr[i + 1])
		return max(a)


class Solution:

	def pairWithMaxSum(self, arr, N):
		mx = -9999999
		for i in range(len(arr) - 1):
			if arr[i] + arr[i + 1] > mx:
				mx = arr[i] + arr[i + 1]
		return mx


import sys

class Solution:

	def pairWithMaxSum(self, arr, N):
		ans = 0
		for i in range(0, N - 1):
			sum = arr[i] + arr[i + 1]
			if sum > ans:
				ans = sum
		return ans


class Solution:

	def pairWithMaxSum(self, arr, N):
		fs = min(arr[0], arr[1])
		ss = max(arr[0], arr[1])
		ms = fs + ss
		for i in range(2, N):
			fs = arr[i - 1]
			ss = arr[i]
			ms = max(ms, fs + ss)
		return ms


class Solution:

	def pairWithMaxSum(self, arr, N):
		s = 0
		ans = -999
		for i in range(N - 1):
			s = arr[i] + arr[i + 1]
			ans = max(ans, s)
		return ans


class Solution:

	def pairWithMaxSum(self, arr, N):
		Sum = 0
		maxSum = -1
		for i in range(N):
			Sum += arr[i]
			if i >= 1:
				maxSum = max(maxSum, Sum)
				Sum -= arr[i - 1]
		return maxSum


class Solution:

	def pairWithMaxSum(self, arr, N):
		max1 = -1
		for i in range(0, len(arr) - 1):
			max1 = max(arr[i] + arr[i + 1], max1)
		return max1


class Solution:

	def pairWithMaxSum(self, arr, N):
		sum = 0
		n = len(arr)
		res = -float('inf')
		for i in range(n - 1):
			sum = arr[i] + arr[i + 1]
			res = max(res, sum)
		return res


class Solution:

	def pairWithMaxSum(self, arr, N):
		m = 0
		maxif = float('-inf')
		for i in range(N - 1):
			m = arr[i] + arr[i + 1]
			maxif = max(maxif, m)
		return maxif


class Solution:

	def pairWithMaxSum(self, arr, N):
		if N < 2:
			return 0
		max_ = arr[0]
		sum_ = 0
		for i in range(len(arr) - 1):
			sum_ = arr[i] + arr[i + 1]
			max_ = max(sum_, max_)
		return max_


class Solution:

	def pairWithMaxSum(self, nums, N):
		maxsub = 0
		for i in range(0, len(nums) - 1):
			cursum = 0
			if cursum < 0:
				cursum = 0
			cursum += nums[i] + nums[i + 1]
			maxsub = max(cursum, maxsub)
		return maxsub


class Solution:

	def pairWithMaxSum(self, arr, N):
		maxi = 0
		for i in range(N - 1):
			sums = arr[i] + arr[i + 1]
			if sums > maxi:
				maxi = sums
		return maxi


class Solution:

	def pairWithMaxSum(self, arr, N):
		i = 0
		s = 0
		while i < N - 1:
			s = max(s, arr[i] + arr[i + 1])
			i += 1
		return s


class Solution:

	def pairWithMaxSum(self, arr, N):
		i = 0
		j = i + 1
		max_sum = -float('inf')
		while i < N and j < N:
			if arr[i] + arr[j] > max_sum:
				max_sum = arr[i] + arr[j]
			j += 1
			i += 1
		return max_sum


class Solution:

	def pairWithMaxSum(self, arr, N):
		curr_sum = 0
		max_sum = 0
		for i in range(0, N - 1):
			curr_sum = max(arr[i], arr[i + 1], arr[i] + arr[i + 1])
			max_sum = max(max_sum, curr_sum)
		return max_sum


class Solution:

	def pairWithMaxSum(self, arr, N):
		res = 0
		for i in range(len(arr) - 1):
			x = arr[i] + arr[i + 1]
			res = max(res, x)
		return res


class Solution:

	def pairWithMaxSum(self, arr, n):
		sum = arr[0] + arr[1]
		maxi = sum
		start = 0
		i = 2
		while i < n:
			sum = sum + arr[i] - arr[start]
			if sum > maxi:
				maxi = sum
			start += 1
			i += 1
		return maxi
		return false


class Solution:

	def pairWithMaxSum(self, arr, N):
		b = []
		for i in range(N):
			if i == N - 2:
				b.append(arr[i] + arr[-1])
				break
			b.append(arr[i] + arr[i + 1])
		return max(b)


class Solution:

	def pairWithMaxSum(self, arr, N):
		ans = 0
		n = len(arr)
		for i in range(n - 1):
			ans = max(ans, arr[i] + arr[i + 1])
		return ans


class Solution:

	def pairWithMaxSum(self, arr, n):
		mx = arr[0]
		for i in range(1, n):
			mx = max(mx, arr[i - 1] + arr[i])
		return mx


class Solution:

	def pairWithMaxSum(self, arr, N):
		maxi = float('-inf')
		for i in range(N - 1):
			maxi = max(maxi, arr[i] + arr[i + 1])
		return maxi