c++ - 为什么我的代码无法处理大型数组输入（> 10000）？

Question

int n;//input size of array
cin >> n;
vector <int> a(n);
vector <int> in;

for (int i = 0; i < n; i++)
    cin >> a[i];//input array elements
if (n == 1) {
    cout << "1" << "\n";
    return 0;
}

for (int i = 1; i <= n ; i++)//to get longest incresing subsequence in the array
{
    int flag = 0, j = i;

    while (j < n && a[j] >= a[j - 1] ) {
        j++;
        flag = 1;
    }
    if (flag == 1) {
        in.push_back(j - i + 1);
        i = j;
    }
}

int maxval = in[0]; //to get maximum sized element from in 
for (int i = 1; i < in.size(); i++)
    if (in[i] > maxval)
        maxval = in[i];
cout << maxval << "\n";

我为 < 10000 的值尝试了相同的代码，它工作正常...我已经用 long long int 替换了所有 int 然后它还显示矢量下标超出范围错误...

样本输入：

10

49532 49472 49426 49362 49324 49247 49165 49162 49108 49093

我期待 0 但它显示“向量下标超出范围”

Answer 1

问题的原因是这个声明

int maxval = in[0];//to get maximum sized element from in 

使用此输入时向量in为空

10

49532 49472 49426 49362 49324 49247 49165 49162 49108 49093

所以你可能不使用下标运算符。

你可以写例如

int maxval = in.empty() ? 0 : in[0];

Answer 2

解决这个问题：

int maxval = in.size()? in[0]:0;

矢量类运算符检查索引是否在数组的下限和上限之间，即 (0 -> size-1)

MSVC 库：

    _NODISCARD _Ty& operator[](const size_type _Pos) noexcept { // strengthened
        auto& _My_data = _Mypair._Myval2;
#if _CONTAINER_DEBUG_LEVEL > 0
        _STL_VERIFY(
            _Pos < static_cast<size_type>(_My_data._Mylast - _My_data._Myfirst), "vector subscript out of range");
#endif // _CONTAINER_DEBUG_LEVEL > 0

        return _My_data._Myfirst[_Pos];
    }

问题是 in.push_back 永远不会被调用，然后大小为零。

所以 in[0] 调用运算符将​​抛出异常索引超出范围。