arrays - 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. 已找到一个新的子数组，其起始位置与之前的最佳子数组不同，因此丢弃旧的 max 并用这个新的取而代之。

您不仅可以跟踪到目前为止的最大子数组，还可以跟踪它的起始位置来实现这一点。如果最大子数组的起始位置与当前数组的位置相同，则属于第 (1) 种情况，否则属于第 (2) 种情况。