how can I optimize this code for a powerline?

Question

I made this code for a past test, I only got 30/100 points obtainable, because it went out of time,how can I make it more efficient?

#include <iostream>
#include <fstream>
bool check(int s[], int n)
{
    for (int i = 0; i < n; i++)
    {
        if (s[i] < s[i + 1] && i != n - 1)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    std::ifstream in("input.txt");
    std::ofstream out("output.txt");
    int n;
    int s[1000000];
    bool legge = false;
    int c = 0;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> s[i];
    }
    legge = check(s,n);
    while (!legge)
    {
        for (int i = 0; i < n; i++)
        {
            int m = i+1;
            if (s[i] < s[m] && i != n-1)
            {
                s[i] = s[m];
            }
        }
        legge = check(s,n);
        c ++;
    }
    out << c;
}

Text: In order to increase their efficiency, a new law mandates that every tower in a power line must be at least as high as the following one. Luca needs to change the height of some towers, in order to meet the new requirements. Every day, starting from the first tower, Luca will increase the height of every tower to the same height of the next one. Of course, if one tower is already taller than the following one it will not be modified. How many days does Luca need to finish the job?

Answer 1

There are several reasons why your solution is slow. However, the main reason is because you are actually performing all the steps that Luca would do, but the goal is just to determine the number of days Luca would need. So try to think of a way to determine that number by just looking at the all the tower heights once.

It helps to look at a few special cases first. Consider the towers having stricly descending heights:

5, 4, 3, 2, 1

It is clear that nothing has to be done, so this would take 0 days. Now look at the towers having strictly ascending heights:

1, 2, 3, 4, 5

It should be fairly obvious that it will take Luca 4 days to fix this, as the result of every day's worth is that it basically shifts the heights to the left, like so:

day 1: 2, 3, 4, 5, 5
day 2: 3, 4, 5, 5, 5
day 3: 4, 5, 5, 5, 5
day 4: 5, 5, 5, 5, 5

So now let's look at a more complex case:

4, 5, 1, 2, 3

The key insight is that there are two distinct regions of increasing heights:

4, 5 and 1, 2, 3

The first region takes one day to fix, the second two days. But this happens in parallel of course, so it's just a matter of finding the largest region of increasing heights, and subtract one from its length to get the number of days Luca needs. There's just one complication, let's look at this example:

2, 3, 1, 4, 5

Again there are two regions of strictly increasing heights, but it should be clear that since the second region's maximum height is larger than the first region's, it will actually take 4 days to finish the job. So what you should do is divide it in regions that each end at the maximum possible height. For example, take this example:

1, 3, 5, 7, 9, 2, 8, 4, 6
            ^     ^     ^
            |     |     |

I marked the positions of the end of each region. The first region's length is 5, the second and third have length 2. So the number of days necessary is 4. But how to find these maxima efficiently? If you scan forward you wouldn't know where the maximum of the first region is until you've seen all numbers. You then need to repeat this for all the points after the maximum. However, if you work backwards you only need to go through the heights once: you keep track of the maximum so far, and how many points you have visited. As soon as you see a height larger than the maximum you have so far, you store the length so far if that is the largest length you've seen so far, and then replace the current maximum with the new maximum you just found:

int maximum = -1; // assuming no tower has negative height
int length = 0;
int longest = 0;

for (int i = n - 1; i >= 0; i--)
{
    if (s[i] > maximum) {
        if (length > longest)
            longest = length;
        maximum = s[i];
        length = 0;
    } else {
        length++;
    }
}

if (length > longest)
    longest = length;

out << longest << "\n";