使用 push_back() 和 pop_back 操作的向量分配如何给出垃圾值

Question

我正在解决一个问题，我必须从数组中找到总和最大的那些元素。但是有一个条件，就是任何两个相邻的元素都不能成为那个最大子数组的一部分。这是我使用简单的蛮力解决方案的代码-

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t != 0)
    {
        int n, i, s, k = 0, m = -1001;
        vector< int > a;
        cin >> n;
        a.resize(n, 0);
        vector< int > b;
        for (i = 0; i < n; i++)
        {
            cin >> a[i];
            m = max(m, a[i]);
            if (a[i] < 0)
            {
                a[i] = 0;
                ++k;
            }
        }
        if (k == n)
            cout << m;
        else
        {
            k = 0;
            s = a[0];
            b.push_back(a[0]);
            for (i = 1; i < n; i++)
            {
                if (i != k + 1)
                {
                    if (a[i])
                    {
                        s += a[i];
                        b.push_back(a[i]);
                        k = i;
                    }
                }
                else
                {
                    if (s - a[i - 1] + a[i] > s)
                    {
                        b.pop_back();
                        s -= a[i - 1];
                        s += a[i];

                        b.push_back(a[i]);

                        ++k;
                    }
                }
            }
        }
        cout << endl;
        for (i = n; i >= 0; i--)
        {
            if (b[i])
                cout << b[i] << " ";
        }
        cout << endl;
        --t;
    }
    return 0;
}

这是代码的输入- 第一行代表没有。测试用例，第二行代表数组的大小下一行显示数组 elements.m

5
5
-1 7 8 -5 4 
4
3 2 1 -1 
4
11 12 -2 -1 
4
4 5 4 3 
4
5 10 4 -1

输出-

4 8 
32 32607 -787829912 1 3 
32 32607 -787829912 12 
3 5 
10

预期输出-

所以，有 5 个测试用例。对于第一个测试用例和最后两个测试用例输出是正确的。但是对于第二个和第三个测试用例，它给出了垃圾值。问题是什么，对于某些测试用例，它给出了垃圾值，而对于其他测试用例则没有。

Answer 1

我想我发现了你的（第一个）问题：

if(k==n)
cout<<m;

当所有数字都是负数时，输出其中最大的一个。

但是空数组的和为0且大于负数，并且其中没有2个相邻成员。很明显，正确答案应该是 0，而不是 m。

Answer 2

    for (i = n; i >= 0; i--)
    {
        if (b[i])
            cout << b[i] << " ";
    }

这将在 b 中打印出 n+1 个值。但即使在最好的情况下，b 也只有 n 个值（对于 n=1）。对于 n>1，b.size() 小于 n，因此您正在从矢量存储外部读取垃圾（这是 未定义的行为 ）。只需使用正确的界限：

for (i = b.size() - 1; i >= 0; ++i)

使用 push_back() 和 pop_back 操作的向量分配如何给出垃圾值

How Vector allocation using push_back() and pop_back operation gives garbage values

c++

vector

push-back

garbage