CODEWITHSUNDEEP
arraysalgorithmtime-complexitymax
Rodrigo
Rodrigo

Reputation: 177

Finding two non-subsequent elements in array which sum is maximal - interview question

The question is similar to here, besides:

  1. We are looking for the maximum.
  2. The answer can contain the first or last element of the array (but not both - because we consider them as adjacent).

My attempt:

I think of using the same idea of RomCoo in the link above, but adjust it to this problem:

  1. Find the largest number.
  2. Find the second largest that is not a neighbour of the first. Then build the sum.
  3. Calculate the sum of both neighbours of the first number. Check if its larger then the first sum. If not: take the first sum, otherwise take the second one.

I believe that the pairs on steps (2) and (3) are the only ones who can make the largest sum, but I can't formally prove it.
If this correct how can you formally prove it?
And if not, how do you solve it?

Upvotes: 1

Views: 523

Answers (2)

Dillon Davis
Dillon Davis

Reputation: 7750

Assume we have two numbers A and B that make up a larger sum. Either A or B (or both) must not be directly adjacent to the largest number, because otherwise they fall into (3). Lets take this to be A, without loss of generality. Since A is not adjacent to our largest number, then B could be safely replaced by our largest number if its not already, resulting in a greater overall sum. Therefore, to be maximal, B must equal our largest number. By the same logic, if there existed a larger value than A not adjacent to our largest number, then this sum would not be maximal either, so A must be the second largest number. This means A and B would fall into (2). So, (2) and (3) are our only valid solutions.

Upvotes: 1

Emma
Emma

Reputation: 27743

I guess the question is "somewhat" similar to 1031 LeetCode question, which you can see it in this link:

Python

class Solution:
    def maxSumTwoNoOverlap(self, nums, l, m):
        for index in range(1, len(nums)):
            nums[index] += nums[index - 1]
        largest = nums[l + m - 1]
        l_max, m_max = nums[l - 1], nums[m - 1]
        for index in range(l + m, len(nums)):
            l_max = max(l_max, nums[index - m] - nums[index - l - m])
            m_max = max(m_max, nums[index - l] - nums[index - l - m])
            largest = max(largest, l_max + nums[index] - nums[index - m], m_max + nums[index] - nums[index - l])

        return largest

Java

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int l, int m) {
        for (int index = 1; index < nums.length; index++)
            nums[index] += nums[index - 1];

        int largest = nums[l + m - 1];
        int lMax = nums[l - 1];
        int mMax = nums[m - 1];

        for (int index = l + m; index < nums.length; index++) {
            lMax = Math.max(lMax, nums[index - m] - nums[index - l - m]);
            mMax = Math.max(mMax, nums[index - l] - nums[index - l - m]);
            largest = Math.max(largest, Math.max(lMax + nums[index] - nums[index - m], mMax + nums[index] - nums[index - l]));
        }

        return largest;
    }
}

For your question, you are gonna have to keep a minimum distance of 2 as you scan your array so that the neighboring section would be addressed. For instance, you maximize for index and index + 2 as you scan or index - 2 and index.

Reference

Here is lee215's answer in Java/Python/C++

Upvotes: 1

Related Questions