c++ - Max SubArray kadane 算法

Question

void kadane(int A[], int N, int& bestStart, int& bestEnd, int& bestSum)
{

    int max_ending_here = 0;
    int max_so_far = 0;
    bestStart = 0;


    for (int i = 0; i < N; i++)
    {

        max_ending_here += A[i];

        if (max_ending_here < 0)
        {
            max_ending_here = 0;
        }
        if (max_ending_here > max_so_far)
        {
            max_so_far = max_ending_here;
            bestEnd = i;
        }

    }
}

我想更新最好的开始索引如果我有一个数组 A={-1,-2,5,0,1} 最好的开始应该是索引 2 和最好的结束索引 4 我得到了最好的结束，但我不知道如何更新这里的最佳起始 Max 子数组 = 6 (5+0+1)

Answer 1

保持潜在的最佳开始指数

bestStartCandidate = 0;

if (max_ending_here < 0)
    {
        max_ending_here = 0;
        bestStartCandidate = i + 1;       
    }
    if (max_ending_here > max_so_far)
    {
        max_so_far = max_ending_here;
        bestStart = bestStartCandidate;       
        bestEnd = i;
    }