最大サブアレイの要素を印刷するKadaneのアルゴリズムが見つかりましたか？

Question

私はKadaneのアルゴリズムを以下のように変更して、配列にすべての負の数がある場合でも動作するようにしました。

//Largest Sum Contiguous Subarray 
#include <iostream> 
#include <map> 
#include <vector> 
#include <string> 
#include <utility> 
#include <algorithm> 

using namespace std; 

#define ll long long 
#define pb push_back 
#define mp make_pair 
#define F(i,a,b) for(int i = (int)(a); i < (int)(b); i++) 
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--) 
#define SIZE 100000 

int main (void) 
{ 
    vector<int> myvec; 
    int arr[SIZE]; 
    int index[SIZE] = {0}; 
    int n; 
    cin>>n; 
    F(i,0,n) 
    { 
     cin>>arr[i]; 
    } 
    int maxendinghere = arr[0]; 
    int maxsofar = arr[0]; 
    F(i,1,n) 
    { 
     if (arr[i] > (arr[i]+maxendinghere)) 
      myvec.pb(i); // used for finding the elements of the subarray 
     maxendinghere = max(arr[i],arr[i]+maxendinghere); 
     maxsofar = max(maxendinghere,maxsofar); 
    } 
    cout<<maxsofar<<"\n"; 
    auto it = myvec.begin(); // printing the subarray 
    while (it != myvec.end()) 
    { 
     cout<<*it<<"\t"; 
     it++; 
    } 
    cout<<"\n"; 
    return 0; 

} 

ここで、サブアレイを構成する実際の要素を印刷しようとしています。私が考えることができることの1つは、毎回(arr[i]+maxendinghere)がarr[i]より大きくなるということです。新しい要素はサブアレイの一部になり、私はそれをベクトルにプッシュして要素を出力します。しかし、これは実際のサブアレイを正しく出力しません。この考え方の過程で私は何が欠けていますか？ありがとう！

PS：これは最高のコーディングスタイルではないと私は理解していますが、これはインタビューで尋ねられ、コード化しようとしていました。私は当時のことができなかったので、これは私が思いつくことができたものです。

編集：回答）templatypypedefによって与えられた答えの後に私はそれをコード化することができました。フォローは実装です。

//Largest Sum Contiguous Subarray 
#include <iostream> 
#include <map> 
#include <vector> 
#include <string> 
#include <utility> 
#include <algorithm> 

using namespace std; 

#define ll long long 
#define pb push_back 
#define mp make_pair 
#define F(i,a,b) for(int i = (int)(a); i < (int)(b); i++) 
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--) 
#define SIZE 100000 

int main (void) 
{ 
    int currsum[SIZE],maxsumsofar[SIZE],sindex[SIZE],eindex[SIZE]; 
    int arr[SIZE]; 
    int start,end,n; 
    cin>>n; 
    F(i,0,n) 
    { 
     cin>>arr[i]; 
    } 
    currsum[0] = arr[0]; 
    maxsumsofar[0] = arr[0]; 
    sindex[0] = 0; 
    eindex[0] = 0; 
    F(i,1,n) 
    { 
     if (arr[i] > (arr[i]+currsum[i-1])) // for starting index 
      sindex[i] = i; 
     else 
      sindex[i] = sindex[i-1]; 

     currsum[i] = max(arr[i],arr[i]+currsum[i-1]); 
     maxsumsofar[i] = max(currsum[i],maxsumsofar[i-1]); 

     if (arr[i] > (arr[i]+currsum[i-1])) 
      eindex[i] = i; 
     else 
     { 
      if (maxsumsofar[i] == maxsumsofar[i-1]) 
       eindex[i] = eindex[i-1]; 
      else 
       eindex[i] = i; 
     } 
    } 
    cout<<maxsumsofar[n-1]<<"\n"; 
    F(i,0,n) 
    { 
     if (maxsumsofar[i] == maxsumsofar[n-1]) 
     { 
      start = sindex[i]; 
      end = eindex[i]; 
      break; 
     } 
    } 
    cout<<"The array lies between indices "<<start<<" to "<<end<<"\n"; 
    return 0; 
} 

Answer 1

Kadaneのアルゴリズムは、部分配列の開始位置を維持し、繰り返し配列の次の要素を見て、

1. は、その要素を追加することで部分配列を拡張し、または
2. のいずれかに決定することによって動作しますサブアレイを破棄し、その要素の後に新しいサブアレイを開始します。

現在のサブアレイの開始点を明示的に追跡すると（最初は配列の最初の要素の前にあり、合計がゼロ以下になるたびにリセットされます）最適なサブアレイを見つける。あなたが見つかった最大部分配列を更新するたびに、いずれかの

1. だけ（そうちょうどあなたがこれまでに見つけた最高のものに追加）、または
2. が発見した既存の最大の部分配列に新しい要素を追加しています前の最適な部分配列とは異なる位置から始まる新しい部分配列です。したがって、古い部分を取り除き、新しい部分配列に置き換えます。

これは、これまでの最大サブアレイだけでなく、その開始位置も追跡することで実装できます。 （1）最大サブアレイがあなたの現在の配列と同じ位置で始まり、そうでなければcase（2）で始まる場合です。