C++ program to find number of increasing peaks

Question

problem--- a peak is defined as in a sequence A=a1,a2,..ai-1,ai,ai+1..an, if ai-1 < ai > ai+1 i.e it is a local maxima , find the number of increasing peaks where an increasing peak is a peak which is greater than all previous peaks.

My approach --- Find all local peaks in the array and push them to a vector. Find the number of increasing peaks by iterating through that vector.

Issue-- Code shows bad_alloc() error while running

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
    int n, i,t, count,x;
    cout << "Enter No of Elements";
    cin >> n;
    int arr[n];
    for (i = 0; i < n;i++)
    {
        cin >> arr[i];
    }
    vector<int> max;
    max.reserve(n);
    if (arr[1]<arr[0]){
        t = arr[0];
        max.push_back(t);
        count = 1;
    }
    for (i = 1; i+1<n;i=i++){
        if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
            t = arr[i];
            max.push_back(t);

    }
    if(arr[n-1]>arr[n-2]){
        t = arr[n - 1];
        max.push_back(t);
    }
    for (i = 1; i < max.size();i++)
    {
        if (max[i]>max[i-1])
            count++;
    }
    cout << count;
    cin >> x;
    return 0;
}

`int arr[n];` -- This is not valid C++. Arrays in C++ must have their size denoted by a compile-time constant, not a runtime variable. You're already using `std::vector`, so use it here: `std::vector arr(n);` — PaulMcKenzie, May 20 '21 at 16:11
Why do you need to store peaks? Can't you just remember the last maximum peak and a count? You probably don't need to store arr either, just process the numbers as you read them in. — Rup, May 20 '21 at 16:12
*Code shows bad_alloc() error while running* -- Where is the test data? — PaulMcKenzie, May 20 '21 at 16:13
And which line gives you the bad_alloc error? The vector declaration or a push_back? — Rup, May 20 '21 at 16:14
You also have some misleading indentation inside that loop. The `if` only covers `t = arr[i];`. `max.push_back(t);` runs every time. — user4581301, May 20 '21 at 16:23
I'm going to toss this into a compiler set to anally retentive and see what warnings pop out: https://godbolt.org/z/hrqsvrqejNothing significant that hasn't already been brought up. — user4581301, May 20 '21 at 16:26
Clang finds the same and the code can't compile under visual studio, so I didn't check it. — user4581301, May 20 '21 at 16:28
See https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H — , May 20 '21 at 16:36

score 1 · Answer 1 · 2021-05-20T16:42:00.247

Firstly, see Why should I not #include <bits/stdc++.h>?.

Secondly, arrays MUST have a constant value. They cannot get their value from any sort of input, etc.

Thirdly, you have an infinite loop:

for (i = 1; i+1<n;i=i++){
        if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
            t = arr[i];
            max.push_back(t);

    }

When we enter the for loop, we begin with i at 1 and (for the example, n will be 3) n with 3. We see all go well, and when we compare 1+1 is smaller than two, so we continue. Next, we post increment i to 2 but, as the post increment returns the value of i before the increment, we reset i to 1! (This is actually undefined behavior, but in your case you got this infinite loop.) Uh oh, that wasn't what we meant, so we fix this code to this:

for (i = 1; i + 1 < n; i++) {
    if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
        t = arr[i];
    max.push_back(t);

}

The increment/decrement already modify int's value, which is why we don't need to assign it. Finally, we have to fix this error:

if (arr[1] < arr[0]) {
    t = arr[0];
    max.push_back(t);
    count = 1;
}

This is a bit tricky, but the user might enter an number like 0, which would cause this to malfunction, while tricking the new operator. To fix this, we can prevent this by replacing:

cin>>n;

With:

while (cin >> n && n < 1);

Which will read into n while n is less than 1;

Also, the reason I used new is because it is what you use for dynamic allocation, or variable sized arrays. This allocates it:

int* arr = new int[n];

and this deallocates it:

delete[] arr;

For more info, read on pointers. Final Result:

#include <string>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, i, t, count, x;
    count = 0;
    cout << "Enter No of Elements";
    while (cin >> n && n < 1);
    int* arr = new int[n];
    for (i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    vector<int> max;
    max.reserve(n);
    if (arr[1] < arr[0]) {
        t = arr[0];
        max.push_back(t);
        count = 1;
    }
    for (i = 1; i + 1 < n; i++) {
        if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
            t = arr[i];
        max.push_back(t);

    }
    if (arr[n - 1] > arr[n - 2]) {
        t = arr[n - 1];
        max.push_back(t);
    }
    for (i = 1; i < max.size(); i++)
    {
        if (max[i] > max[i - 1])
            count++;
    }
    cout << count;
    cin >> x;
    return 0;
}

Also, I initialized count, because it was only being initialized in the if.

Note: Quoting @user4581301

note on the use of new here. Prefer std::vector when you need a dynamic array. std::vector automates the allocation and deallocation with RAII so you can be sure you have no leaks.

A note on `i=i++`: The behaviour is undefined. In this case it appears the asker got an infinite loop, but you can't count on always getting an infinite loop. — user4581301, May 20 '21 at 16:36
A note on the use of `new` here. Prefer ` std::vector` when you need a dynamic array. `std::vector` automates the allocation and deallocation with [RAII](https://stackoverflow.com/questions/2321511/what-is-meant-by-resource-acquisition-is-initialization-raii) so you can be sure you have no leaks. — user4581301, May 20 '21 at 16:38
@user4581301 That is true, but to keep it as similar to the original code, I will keep it like this. If you like, I will add a note advising on this. — , May 20 '21 at 16:39
Worth an edit to point out the `max.push_back(t);` in the loop of doom always runs. — user4581301, May 20 '21 at 16:40
And at this point you might be able to see why I didn't answer this question myself: To cover all of the little mistakes the answer goes on for pages. [mre]s rock. — user4581301, May 20 '21 at 16:41

C++ program to find number of increasing peaks

1 Answers1