You have a lightbulb for an interval of $N$ seconds, where $N$ is given. At time 0, the lightbulb switches on, and at time $N$, it switches off, regardless of any switches. From time 1 to time $N-1$ you have a maximum of $N-2$ switches in the form of an array called switches, which turn the lightbulb to the opposite of what it currently is i.e. if it's on it'll turn off and vice versa. For example, suppose $N = 8$ and switches $[1,2]$. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain on until time 8, when it turns off. Hence, the time it remains on is equal to $1-0 + 8-2 = 7$.
Now suppose you have to insert a switch in this interval, where there is not already a switch present. What is the maximum time the lightbulb remains on once you insert the switch. For example, in the above case, the solution would be 6 since inserting a switch at time 7 keeps the time the lightbulb spends on maximum. Since $1-0 + 7-2 = 6$, the answer is 6.
I solved this using a brute force solution, using the reasoning that if you insert a switch at time $k$, the states of the lightbulb before this wouldn't be affected, and the states of the lightbulb from time $k$ to time $N$ will be reversed, and hence you can find the time it spends on after time $k$ by $(N - k) - t$, where $t$ is the time it would spend on from time $k$ to $N$ without the inserted switch. Hence, I can calculate the time the lightbulb would spend on for each time position of the inserted switch and maximize it. However, since calculating the time the lightbulb spends on is $O(n)$ operations and I go through all possible positions, my solution is $O(n^2)$ and this caused my code to time out for some test cases.
Can someone propose a better solution?