Java 从数组时间复杂度中求最大值

Question

有一个包含 N 个元素的整数数组 A，例如 {4, 2, 11, -2, 1} 我需要从每个子数组中找到具有最大值的元素。子数组是这样生成的：

for i = 0, leftArray = {4} , rightArry = {2,11,-2,1} 
for i = 1, leftArray = {4,2}, rightArry = {11,-2,1}
for i = 2, leftArray = {4,2,11}, rightArry = {-2, 1}
for i = 3, leftArray = {4,2,11,-2}, rightArry {1}

所以，我需要这样的东西：

for (int i = 0; i < A.length; i++){
   //LOGIC HERE
    System.err.println(String.format("Left array max = %s, Right array max = %s",lmax, rmax));
}

如果我们不关心时间复杂度，这就不是问题， 但预期的最坏情况时间复杂度为 O(N)

我不知道如何使用 O(N) 算法实现此目的。任何帮助将不胜感激。

编辑：

我目前的解决方案：

for (int i = 0; i < A.length; i++)
        {
            if(i  == A.length - 1)
                break;

            int[] l = Arrays.copyOfRange(A, 0, i + 1);
            int[] r = Arrays.copyOfRange(A, i + 1, A.length);

            Arrays.sort(l);
            Arrays.sort(r);
            System.err.println(l[l.length -1] + " " + r[r.length - 1]);
        }

Answer 1

这在 O(n) 中是可能的，但我只能想到如何分两遍找到最大值，然后再打印一遍：

int[] leftMaxes = new int[A.length - 1];
int[] rightMaxes = new int[A.length - 1];

leftMaxes[0] = A[0];
for (int i = 1; i < A.length - 1; ++i) {
  leftMaxes[i] = Math.max(leftMaxes[i-1], A[i]);
}

rightMaxes[A.length - 2] = A[A.length - 1];
for (int i = A.length - 3; i >= 0; --i) {
  rightMaxes[i] = Math.max(rightMaxes[i+1], A[i+1]);
}

for (int i = 0; i < A.length - 1; ++i) {
  System.out.printf("%d: %d %d%n", i, leftMaxes[i], rightMaxes[i]);
}

Ideone demo

输出：

您可以组合 leftMaxes 和打印循环（先执行 rightMaxes）以删除其中一个通道；但这对于所需的复杂性来说不是必需的。

您可以组合使用 rightMaxes 和 leftMaxes 循环，但我认为这会使代码更难阅读。

Java 从数组时间复杂度中求最大值

Java finding maximum from array time complexity

java

arrays

algorithm

big-o

time-complexity