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）。