配列の時間の複雑さから最大のJavaを見つける

Question

N個の要素、例えば{4,2,11、-2,1}の配列Aを持つと、すべてのサブ配列から最大値を持つ要素を見つける必要があります。

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} 

だから、私はこのようなものが必要です：サブ配列はこのように生成され、我々は時間の複雑さを気にしない場合、これは問題になるwould't

を

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)); 
} 

BUT期待される最悪ケースの時間複雑度はO（N）

私はO（N）アルゴリズムでこれをどのようにして実現するのか分かりません。どんな助けもありがとう。

EDIT：

私の現在のソリューション：

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）の中で可能ですが、私は唯一のmaxesを見つけるために、2回のパスでそれを行う方法を考えることができ、その後、別のパスそれらを印刷します

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

出力：

0: 4 11 
1: 4 11 
2: 11 1 
3: 11 1 

あなたはパスのいずれかを削除するには（rightMaxes最初のをやって）leftMaxesと印刷のループを組み合わせることができ、それは必要な複雑さのために必要ではありません。

そして、rightMaxesループとleftMaxesループを組み合わせることもできますが、コードを読むのがずっと難しくなると思います。