与えられた2次元配列の連続した部分配列の最大和

Question

私はこの問題を解決しましたが、与えられた説明はすべて少なくともN^3の複雑さを持つDP解で与えられます。私はN^2でそれを解決しました。私の解決策が間違っているのだろうかと思っています。

整数の2次元配列（+ veと-ve）が与えられていますが、2つは可能な限り最大の和を持つこの配列の部分配列です。

私が使ったアルゴリズムは、4つのインデックスを修正することです。 2列の場合、私は0からNまでスパンして、最大合計がどこで発生するかを調べ、次にNから0までスパンします。これらの2つの結果から、どの列から合計が最大になるか推測します。 S 同じ方法を行に使用します。一度、私は4つの指標を得る、私は完了です。 複雑さ：ここではO（N^2）

は私のコードです：

#include <iostream> 

using namespace std; 

template<size_t n> 
int find_col_sum(int A[][n], int m, int r1, int r2, int c) { 
    int sum = 0; 
    for (int i = r1; i <= r2; i++) 
     sum += A[i][c]; 
    return sum; 
} 
template<size_t n> 
int find_row_sum(int A[][n], int m, int c1, int c2, int r) { 
    int sum = 0; 
    for (int i = c1; i <= c2; i++) 
     sum += A[r][i]; 
    return sum; 
} 

template<size_t n> 
void max_sum_array(int A[][n], int m, int &i1, int &i2, int &i3, int &i4) { 
    int mx1 = 0, mx2 = 0; 
    int sum = 0, max1_sum = 0; 
    int max2_sum = 0; 

    //0 to col 
    for (int i = 0; i < n; i++) { 
     sum += find_col_sum(A,m,0,n-1,i); 
     if (sum > max1_sum) { 
      mx1 = i; 
      max1_sum = sum; 
     } 
    } 
    //n-1 to col 
    sum = 0; mx2 = n-1; 
    for (int i = n-1; i >= 0; i--) { 
     sum += find_col_sum(A,m,0,n-1,i); 
     if (sum > max2_sum) { 
      mx2 = i; 
      max2_sum = sum; 
     } 
    } 
    if (mx1 <= mx2) { 
     if (max1_sum >= max2_sum) { 
      mx2 = mx1; mx1 = 0; 
     } 
     else { 
      mx1 = mx2; mx2 = n-1; 
     } 
    } 
    else 
     swap(mx1,mx2); 
    i1 = mx1; i2 = mx2; 
    mx1 = 0; mx2 = m-1; 
    max1_sum = 0; max2_sum = 0; 
    sum = 0; 
    //0 to row 
    for (int i = 0; i < m; i++) { 
     sum += find_row_sum(A,m,i1,i2,i); 
     if (sum > max1_sum) { 
      mx1 = i; 
      max1_sum = sum; 
     } 
    } 
    sum = 0; 
    //m-1 to row 
    for (int i = m-1; i >= 0; i--) { 
     sum += find_row_sum(A,m,i1,i2,i); 
     if (sum > max2_sum) { 
      mx2 = i; 
      max2_sum = sum; 
     } 
    } 
    if (mx1 <= mx2) { 
     if (max1_sum >= max2_sum) { 
      mx2 = mx1; mx1 = 0; 
     } 
     else { 
      mx1 = mx2; mx2 = m-1; 
     } 
    } else 
     swap(mx1,mx2); 
    i3 = mx1; i4 = mx2; 
} 

int main() { 
    int A[][4] = {{0,-2,-7,0},{9,2,-6,2},{-4,1-4,1},{-1,8,0,-2}}; 
    int i1 = 0, i2 = 0, i3 = 0, i4 = 0; 

    max_sum_array(A,4,i1,i2,i3,i4); 
    cout<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<endl; 

    return 0; 
} 

Answer 1

それは間違っています。たとえば、配列が{{-1, -1, -1}, {-1, 1, -1},{-1, -1, -1}}の場合は0 0 0 0を出力し、正解の場合は1 1 1 1（中間の要素を唯一の肯定的なものとして取ることが最適です）を出力します。

正しいO（n^3）解決策は次のとおりです。 上の行を修正しましょう。ゼロの配列を作成しましょう。今度は、この行から最後の行まで行を繰り返します。各行を配列に追加し、この配列の1次元解を呼び出します。上の行をすべて確認したら、最大の答えを印刷するだけです。