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; 

} 

現在，我試圖打印形成子數組的實際元素。我能夠想到的一件事是，每次(arr[i]+maxendinghere)將大於arr[i]，一個新的元素將成爲子陣列的一部分，我將它推入矢量並打印元素。但是這並沒有正確地給出實際的子陣列。我在這個思考過程中失去了什麼？謝謝！ PS：我知道這不是最好的編碼風格，但是這是在採訪中提出的，我試圖對它進行編碼。那時我不能回頭，因此這就是我所能想到的。

編輯：答案）我能夠在templatetypedef給出的答案後進行編碼。以下是實施。

//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），否則就是（2）。