Maximum_Score_from_Subarray_Minimums_brute_force.py

""" O(n*n) approach """
class Solution:
    def pairWithMaxSum(self, arr):
        # Your code goes here
        nums = arr
        globalMaxSum = float('-inf')
        n = len(nums)
        
        for i in range(n-1):
            fMin = nums[i]
            for j in range(i+1, n):
                sMin = nums[j]
                if nums[j] < fMin:
                    sMin = fMin
                    fMin = nums[j]
                elif nums[j] < sMin:
                    sMin = nums[j]
                # print(i, j, fMin, sMin)
        
                currentSum = fMin + sMin
                globalMaxSum = max(globalMaxSum, currentSum)
                
        return globalMaxSum
    

Maximum_Score_from_Subarray_Minimums_optimal.py

""" O(n) approach """
class Solution:
    def pairWithMaxSum(self, arr):
        # Your code goes here
        globalMaxSum = float('-inf')
        
        for i in range(len(arr)-1):
            globalMaxSum = max(globalMaxSum, arr[i] + arr[i+1])
            
        return globalMaxSum