Maximum sum of smallest and second smallest in an array

Given an array, find maximum sum of smallest and second smallest elements chosen from all possible subarrays. More formally, if we write all (nC2) subarrays of array of size >=2 and find the sum of smallest and second smallest, then our answer will be maximum sum among them. Examples:

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

Input : arr[] =  {5, 4, 3, 1, 6}
Output : 9
class Solution {
    // Because we want max sum of 2 smallest elements in subarrays
    // We can just consider all 2 size subarrays, because these are the ones that
    // can provide max sum
    public int pairWithMaxSum(int[] arr, int N) {
        if (N < 2)
            return -1;
        // Find two consecutive elements with maximum sum.
        int res = arr[0] + arr[1];
        for (int i = 1; i < N - 1; i++)
            res = Math.max(res, arr[i] + arr[i + 1]);
        return res;
    }
}

Last updated