Max Score from Subarray Mins

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Maximize score = min(arr[i], arr[j]) * (i+j) over all pairs i < j. Greedy or sorted pairs.

Algorithm

1For adjacent pairs, min is more predictable. Consider all adjacent pairs: score = min(arr[i], arr[i+1]) * (i+i+1).

Common Pitfalls

•Adjacent elements maximize score because non-adjacent pairs have smaller min. O(n) scan of adjacent pairs.

Max Score from Subarray Mins.java

Java

// Approach: For each pair of adjacent elements, their sum is a candidate (no non-adjacent sum can be better).
// Time: O(n) Space: O(1)
class Solution {
    public int maxSum(int arr[]) {
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++)
            ans = Math.max(ans, arr[i] + arr[i - 1]);

        return ans;
    }
}

Was this solution helpful?