c++ - 如何修复此代码我尝试了很多方法*悲伤*

一般技术：

第 1 步：从输入初始化

将 OP 给出的样本值作为输入集

15 666
101 42 -132 17 404 -13 55 222 89 11 -66 91 -9 21 4

初始化 N、S 和 A 的值很容易。这很容易：

int N, S;  // N=count of items to be read, S is the max sum constraint of the longest subsequence
vector<int> A;  // array of integers, vector is convenient in C++

cin >> N >> S;

A.resize(N);

for (int i = 0; i < N; i++)
{
    cin >> A[i];
}

第 2 步：从原始输入数组创建一个求和数组。

求和数组是长度等于的数组A。每个元素SUM[i]都分配有以下值：

 SUM[0] = A[0]
 SUM[1] = SUM[0] + A[1]
 SUM[2] = SUM[1] + A[2]
 SUM[3] = SUM[2] + A[3]
 ...

它本质上是一个数组，表示A.

vector<int64_t> summations;
int64_t sum = 0;
for (int i = 0; i < N; i++)
{
   sum += A[i];
   summations.push_back(sum);   
}

例如，原始项目数组：

         A[] = 101  42 -132 17 404 -13  55 222  89  11 -66  91  -9  21   4

变成：

summations[] = 101 143   11 28 432 419 474 696 785 796 730 821 812 833 837

现在要找到从开始的最长子序列（ sum <= S），A[0]代码只需从summations数组的右侧扫描，直到<=S找到第一个值。如果在求值后没有找到这样的值summations[0]，则没有从索引 0 开始的可行序列。在这种情况下，求和数组右侧的第一个值<= 666位于summations[6]，即474。因此，来自A[0] - A[6](length: 7) 的序列的总和为474并且是总和小于S(666) 的最长子序列的候选者。

然后测试是否A[1]有更好的候选序列，不需要对数组进行修改。只需添加A[0]并S再次从右侧重复扫描，直到<=S遇到一个值或直到索引 1 被命中。在这种情况下，扫描一个小于的值767在summations[11]，即730。所以现在的10项目序列A[1] to A[11]是找到的最佳序列。

我们可以对整个项目数组重复这个算法。再次，添加A[1]并S重复扫描，summations[N-1]直到summations[2]确定从 ... 开始的最长序列A[2]。

但是，对于大型输入数组，这将无法扩展。问题表明输入数组中可能有超过 500000 个项目。即使进行了一些优化，这也需要很长时间才能扫描。它仍然有O(N²)运行时间。该算法将从序列数组的末尾线性地重复重新评估相同的数字。必须有一种更好的方法来找到最接近末尾的 summations 数组中的值，即 <= S 施加的值。所以让我们来探讨一下......

第 3 步：从 summations 数组构建二叉树

现在构建一个二叉树。每个节点包含 4 个值：求和数组中项目的低/高索引值以及该序列范围内的最小和最大元素。让我们看看我们是否可以在 ascii 中绘制出它的样子

                                                                                            {[0-14],11,837}
                                                         /------------------------------------             --------------------------------\
                                           {[0-7],11,696}                                                                                   {[8-14],730,837}
                              /------------             -----------\                                                             /-----------              ---------\
                {[0-3],11,143}                                      {[4-7],419,696}                               {[8-11],730,821}                                   {[12-14],812,837}  
               /             \                                      /             \                               /              \                                   /               \
{[0-1],101,143}               {[2-3],11,28}          {[4-5],419,432}               {[6-7],474,696}  {[8-9],785,796}               {[10-11,730,821}  {[12-13],812,833}                 {[14-14],837,837}
    101 143                        11 28                  432 419                       474 696          785 796                        30 821           812 833                             837

第 4 步 - 使用二叉树S在 summations 数组中搜索最后一次出现的值 <=

现在使用上面的二叉树，我们可以搜索summations数组中小于或等于S（或任何值）的最后一个值。只需从根节点开始，并通过访问正确的节点来进行深度拳头遍历，当您遇到引用summations符合条件的项目的叶节点时首先停止。

因此，首先，我们可以轻松地在根节点处向下遍历树，寻找最大的索引 <= 666。我们查看第一个右孩子，{[8-14],730,837}发现目标值 666 不会被找到，所以我们访问{[0-7],11,696}next ，然后{[4-7],419,696}，{[6-7],474,696}然后我们可以很容易地找到474索引 6。

后续迭代类似于步骤2中的数组遍历方法。要评估A[1]作为起点，我们需要加A[0]回S并再次遍历树。这次一个值得注意的例外是我们必须指定一个“左边缘”，1因此我们不考虑开始索引之前的值。不应该对小于左边缘的值进行任何遍历。随着额外的迭代完成，左边缘也会增加。

搜索代码如下所示：


struct node
{
    bool isLeaf;
    shared_ptr<node> left;
    shared_ptr<node> right;
    size_t indexFirst; // index of first element from array
    size_t indexLast;  // index of last element from array
    int64_t minValue;
    int64_t maxValue;

    bool search(const vector<int64_t>& summations, int64_t maxSum, size_t leftEdge, size_t& resultIndex)
    {
        if (this->indexLast < leftEdge)
        {
            return false;
        }

        if (maxSum < this->minValue)
        {
            return false;
        }

        if (this->isLeaf)
        {
            // seach the summation array looking for the largest index referencing a value <= maxSum

            bool found = false;

            for (size_t i = indexFirst; i <= indexLast; i++)
            {
                if (summations[i] <= maxSum)
                {
                    found = true;
                    resultIndex = i;
                }
            }
            return found;
        }

        // visit the right node first to find values that are less than or equal to maxSum, but at higher index numbers
        if (this->right != nullptr)
        {
            if (this->right->search(summations, maxSum, leftEdge, resultIndex))
            {
                return true;
            }
        }

        if (this->left != nullptr)
        {
            return this->left->search(summations, maxSum, leftEdge, resultIndex);
        }

        // assert - we should never get here
        ASSERT(false);
        return false;
    }
}

然后是重复搜索后续起始索引点的代码：

auto spRootNode = previousRow[0];

// now comes the fun part
// consider every index to be the starting point of the longest sequence, adjusting maxSum as we go along

int64_t target = S; // MAX SUM target
size_t bestStart = 0;
size_t bestLength = 0;
int64_t bestSum = 0;
int64_t dropSum = 0;
for (size_t i = 0; i < summations.size(); i++)
{
    size_t bestPossibleLength = summations.size() - i;
    if (bestLength >= bestPossibleLength)
    {
        break; // no point in continuing
    }

    size_t resultIndex = 0;
    bool resultFound = spRootNode->search(summations, target, i, resultIndex);

    if (resultFound)
    {
        size_t length = resultIndex - i + 1;
        if (length > bestLength)
        {
            bestStart = i;
            bestLength = length;
            bestSum = summations[resultIndex] - dropSum;
        }
    }

    target += A[i]; // add from the items array, not the summations array
    dropSum += A[i];
}

以上运行时间大约为O(N lg N)。

c++ - 如何修复此代码我尝试了很多方法悲伤

问题描述

解决方案

推荐阅读