C++ - 配列内の2つの要素とそれらのインデックスの合計を最大化する

Question

O（N）のプログラミング謎を解決するにはどうすればよいですか？整数の

アレイ：Tab[N]
私が思い付くことができ0 <= K <= L <= N

唯一の解決策は、私は各要素を比較し、最大合計を更新O(N^2)あるmax(Tab[K] - K + Tab[L] + L)
を探します。

一般に

Answer 1

int curr_max = INTEGER_MIN; 
for(int i = 0; i < N; i++){ 
    for(int j = i; j < N; j++){ 
     curr_max = max(Tab[i]-i + Tab[j] + j,curr_max); 
    } 
} 

起因K<=L制約に、タスクのこの種を解決するための可能な方法は、予め計算走行maxを使用することです。 （以下のバージョンが最適化された、とにかくO(N)時間と空間の複雑さを持つことができます。）

int t[N+1]; // input 

int a[N+1]; // running max t[i]-i, left to right 
a[0] = t[0]-0; 
for (int i = 1; i <= N; ++i) 
    a[i] = max(a[i-1], t[i]-i); 

int b[N+1]; // running max t[i]+i, right to left 
b[N] = t[N]+N; 
for (int i = N-1; i >= 0; --i) 
    b[i] = max(b[i+1], t[i]+i); 

int mx = a[0] + b[0]; 
for (int i = 1; i <= N; ++i) 
    mx = max(mx, a[i] + b[i]); 

しかし、我々の場合には、それがK: Tab[K]-K -> max場合、その後L: Tab[K]+K -> maxK<=Lことを示すことができます。換言すれば、LおよびKがそれぞれ2つの最大値のインデックスである場合、プロパティL<=Kが成立する。したがって、ナイーブなアプローチは、あまりにも動作するはずです：

int K = 0, L = 0; 
for (int i = 1; i <= N; ++i) { 
    if (t[i]-i > t[K]-K) 
     K = i; 
    if (t[i]+i > t[L]+L) 
     L = i; 
} 
assert(K <= L); 
int mx = t[K]-K + t[L]+L; 

Answer 2

方法について：それはK < = Lを検証していない、どちらも問題のコードを実行していないこと

int L_max = INTEGER_MIN; 
int K_max = INTEGER_MIN; 

for(int i=0; i<N; i++) 
{ 
    K_max = max(Tab[i] -i, K_max); 
    L_max = max(Tab[i] +i, L_max); 
} 
curr_max = K_max + L_max; 

注意。