Given an array of integers, nums, and an integer k, find the maximum sum of two elements in nums less than k. Otherwise, return $−1$ if no such pair exists.

Constraints:

• $1\leq$ nums.length $\leq100$

• $1\leq$ nums[i] $\leq 10^3$

• $1\leq$ k $\leq 10^3$

This solution uses the following approaches to find the maximum of the two values, which is less than k.

1. Sorting: The array is first sorted in ascending order to facilitate the binary search and avoid checking every possible pair.

2. Binary Search: For each number in the sorted array, a binary search is performed to find the largest number after the given index such that the sum of the two numbers is less than k. This narrows the search space, reducing the time complexity compared to brute force.

3. Tracking Maximum: As the solution iterates through the array and finds two numbers whose sum is less than k, the result is updated with the maximum sum that meets the condition.

Here’s the step-by-step implementation of the solution:

1. Initialize a variable maximum_sum to store the maximum sum.

2. Sort the nums to help binary search find two numbers whose sum is less than k, without searching through the whole array.

3. Iterate through nums, and for each nums[i]:

   1. Calculate the target k - nums[i].

   2. Call the search function to find the largest index j > i such that nums[i] + nums[j] is less than k.

   3. If two numbers are found (i.e., j > i), update the maximum_sum with the maximum sum found so far.

4. Return the maximum_sum which represents the maximum sum, if there is any. Otherwise, $-1$ is returned.

The helper function search uses binary search to find the index j such that the sum nums[i]+nums[j] < k. It takes the nums array, target value, and the start range of the search as input and performs the following steps:

1. Initialize left to start and right to the last index in the nums.

2. Initialize result to store the index j.

3. Perform binary search until left exceeds right:

   1. Calculate the midpoint, mid, between left and right.

   2. If nums[mid] < target, update result to mid and move left to mid + 1 to look for larger values.

   3. If nums[mid] >= target, move right to mid - 1 to check smaller values.

4. Return result which represents the index j such that nums[j] < target.

Let’s look at the following illustration to get a better understanding of the solution: