找到(i，j)对，使i<j和and (a[i] + a[j])最大

Question

给定一个未排序的数组- arr找到一对arri和arrj，使得arr[i] < arr[j] & i<j和arrj是最大的。

预期时间复杂度- O(n)

对于阵列a = {4, 1, 3, 2, 5, 3}

pair is (4, 5).

下面是我尝试过的代码。

void findPair(int[] a){  
        int n = a.length;
        int max = a[0];
        int secondMax = Integer.MIN_VALUE;

        for(int i=1; i<n; i++){
            if(a[i]>max){
                secondMax = max;
                max = a[i];
            }
        }
        if(secondMax == Integer.MIN_VALUE){
            System.out.println("-1 -1");
        }
        else{
            System.out.println(secondMax+" "+max);
        }
}

Answer 1

这是一个使用堆栈的解决方案。其思想是堆栈始终包含一个降序序列，这样对于您查看的每个数字，它都可以与堆栈中比它低的最大数字配对。

在使用数字时将其弹出是安全的，因为例如，如果你有一个6，堆栈的顶部是3，那么就没有必要保留3，以防它可以与更大的数字配对；如果后面有7，你将等待它与6而不是3配对。

public void solution(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    int bestX = -1, bestY = -1, bestSum = -1;

    for(int y : arr) {
        while(!stack.isEmpty() && stack.peek() < y) {
            int x = stack.pop();
            if(x + y > bestSum) { bestX = x; bestY = y; bestSum = x + y; }
        }
        stack.push(y);
    }

    System.out.println(bestX + " " + bestY);
}

尽管有嵌套循环，但时间复杂度为O(n)，因为内部循环总是从堆栈中弹出，并且每个元素只被推入一次，因此它只能被弹出一次。

Answer 2

我仔细考虑了你的问题，我想我找到了一个可以接受的解决方案。

您应该从数组的末尾(右侧)开始将数组拆分为多个子数组。构建子数组是以迭代的方式进行的。您从最右边的数字开始，然后将他之前的所有低于他的数字添加到子数组中。当您达到一个大于/等于子数组中最右边的数字时，迭代将转到下一个子数组。

示例：

你的数组是：{1,7,3,4,5,4,6,2}

输出应为：(5,6)

拆分应该是：

{{1，7}，{3，4，5，4，6}，{2}}

  <--(3)     <--(2) <--(1)

从最后一个值为2的索引开始，它前面的数字是6，所以这是第一个子数组的结尾。接下来，你从6开始，他之前的所有数字都小于6，所以你把它们加到那个子数组中。最后一个子数组以7开始并加1。请参阅箭头以了解详情。

接下来，在每个子数组中检查从左到右哪个数字是最大的，并将其标记为与最右边的数字可能的配对。

在我们的示例中，它是：(1，7)，(5，6)。

因为{2}只有一个变量，所以只有两个选项。在最右边为6的子数组中，最大值为5，而在最右边为7的子数组中，1是唯一的另一个数，因此它也是最大值。

如果没有找到配对，则返回"no possible pair found“。

最后，检查sum并返回最大对：(5,6)

1+7 = 8 < 5+6 = 11

为什么这是O(n)

扫描阵列一次以进行拆分:扫描大小为O(n)

• Each的子数组扫描所有子数组的最大值：O(d)

• Sum of d：O(n)

总计：O(n)

我不擅长Java，所以我的代码可以用Python编写，转换应该很容易(因为Python很容易！)。如果你想要Python代码，请让我知道，我会为你写一些。此外，我还可以更多地解释为什么这个算法有效(如果没有完全理解)。

Answer 3

免责声明:解决方案是O(n^2)，而不是OP要求的O(n)

使用2个嵌套循环如何：

从

• i到
• j从i+1到a.length

从0到0

这可确保i<j随后具有if以确保a[i]<a[j]并找到最大值

int currentMax = -1;
int foundI = -1;
int foundJ = -1;
for(int i=0; i<a.length; i++) {
    for(int j=i+1; j<a.length; j++) {
        if(a[i] < a[j] && a[i] + a[j] > currentMax) {
            currentMax = a[i] + a[j];
            foundI = i;
            foundJ = j;
        }
    }
}

输出：

System.out.println("i:" + foundI);
System.out.println("j:" + foundJ);
System.out.println("a[i]:" + a[foundI]);
System.out.println("a[j]:" + a[foundJ]);
System.out.println("sum:" + currentMax);

i:0
j:4
a[i]:4
a[j]:5
sum:9