Maximum Score From Subarray Mins

Problem Statement

You are given an array arr[] of integers. Your task is to find the maximum sum of the smallest and second smallest elements across all subarrays (of size >= 2) of the given array.

Input cases

Examples :

Input: arr[] = [4, 3, 5, 1]
Output: 8
Explanation: All subarrays with at least 2 elements and find the two smallest numbers in each:
[4, 3] → 3 + 4 = 7
[4, 3, 5] → 3 + 4 = 7
[4, 3, 5, 1] → 1 + 3 = 4
[3, 5] → 3 + 5 = 8
[3, 5, 1] → 1 + 3 = 4
[5, 1] → 1 + 5 = 6
Maximum Score is 8.
Input: arr[] = [1, 2, 3]
Output: 5
Explanation: All subarray with at least 2 elements and find the two smallest numbers in each:
[1, 2] → 1 + 2 = 3
[1, 2, 3] → 1 + 2 = 3
[2, 3] → 2 + 3 = 5
Maximum Score is 5

Constraints:

2 ≤ arr.size() ≤ 10^5
1 ≤ arr[i] ≤ 10^6

Intuition

Instead of iterating through all possible subarrays and finding the smallest and second smallest elements (which is inefficient), we can simplify the problem using the following observation:

To maximize the sum of the two smallest elements in a subarray, both of them should be as large as possible.

This naturally leads us to a key insight:

Key Insight:

Among all subarrays of size ≥ 2, the ones with only 2 elements are sufficient to check.

Why? Because:

In a longer subarray (size ≥ 3), the two smallest elements tend to be smaller, hence their sum is also smaller.

With just 2 elements, we know the smallest and second smallest directly — it's just the two numbers themselves.

Steps

• Initialize a variable maxSum to 0.

• Loop through the array and for every adjacent pair, calculate their sum.

• Update maxSum with the maximum of the current sum and the existing maxSum.

• Return maxSum at the end.

Time and Space Complexity

Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(1) as no extra space is used.

Code

class Solution {
    public int maxSum(int arr[]) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int maxSum = 0;
        int length = arr.length;
        for (int index = 0; index < length - 1; index++) {
            maxSum = Math.max(maxSum, arr[index] + arr[index + 1]);
        }
        return maxSum;
    }
}