why my code is unable to handle large array input(>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";

I tried the same code for values < 10000 it's working fine...i've replaced all int's by long long int's then also it's showing vector subscript out of range error...

Sample input :

10

49532 49472 49426 49362 49324 49247 49165 49162 49108 49093

i'm expecting 0 but it shows "vector subscript out of range"

Make this mistake often enough and you'll learn that <= in looping code is always a code-smell. — Hans Passant
– Hans Passant, Commented Nov 11, 2019 at 16:28
i'm expecting 0 but it shows "vector subscript out of range" -- What is the issue understanding this error? The error is self-explanatory. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 11, 2019 at 16:31
Aside: the final loop can be replaced by std::max_element (found in <algorithm>) — Caleth
– Caleth, Commented Nov 11, 2019 at 16:35
Honestly, I don't know why this is getting upvoted. The error should be obvious in terms of what it is stating. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 11, 2019 at 16:56

Vlad from Moscow · Accepted Answer · 2019-11-11 16:35:47Z

7

The reason of the problem is this statement

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

The vector in is empty when this input is used

10

49532 49472 49426 49362 49324 49247 49165 49162 49108 49093

So you may not use the subscript operator.

You could write for example

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

edited Nov 11, 2019 at 16:35

answered Nov 11, 2019 at 16:34

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Caleth Over a year ago

alternatively, they could change if (flag == 1) { in.push_back(j - i + 1); i = j; } to in.push_back(j - i); i = j;

Ahmed Anter · Accepted Answer · 2019-11-12 12:07:04Z

2

Fix this:

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

the vector class operator checks the index is between lower and upper limit of array which will be (0 -> size-1)

MSVC lib:

    _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];
    }

the problem is that the in.push_back never get called then the size is zero.

so in[0] call operator will throw exception index out range.

edited Nov 12, 2019 at 12:07

answered Nov 11, 2019 at 16:39

Ahmed Anter

6504 silver badges13 bronze badges

6 Comments

underscore_d Over a year ago

An answer should explain what was wrong and how it resolves that. Anyway, this just repeats what Vlad already wrote, in a less clear way. (I didn't downvote, fwiw.)

underscore_d Over a year ago

"vector class operator checks the index" operator[] does not have to check anything. The fact that it sometimes does in debug builds produced by some compilers should not be relied upon. If an index might be out of bounds at runtime and is not controllable, the user must use .at() to ensure that the index is checked and an exception thrown if invalid. operator[] makes no guarantee and is free to turn your entire program into undefined behaviour if it receives an invalid index, so only users who are confident what they are doing should use it.

Ahmed Anter Over a year ago

you are right but he is getting exception and here is the operator definition:

Ahmed Anter Over a year ago

_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]; }

Ahmed Anter Over a year ago

so he is building debug build

|

Collectives™ on Stack Overflow

why my code is unable to handle large array input(>10000)?

2 Answers 2

1 Comment

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related