Interview Question: Insert switch to maximize time lightbulb spends on Problem statement:  


  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?
Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:


Note1 If a[i+1] = a[i] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.



Note2 The optimal value we add between $a[i]$ and $a[i + 1]$  for some $i$ is either equal to $a[i] + 1$ or to $a[i+1] - 1$.
Proof. Assuming the claim is not true, there is an optimal value strictly between $a[i]+1$ and $a[i+1]-1$. However, if the bulb is turned off in this interval we can push it back to $a[i]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a[i+1]-1$ increasing the length of turned on pulp in this interval.


So now we can loop over the array, and for each $i$, if $a[i] \neq a[i+1]-1$, we try to add the value $a[i]+1$ and the value $a[i+1]-1$, these are 2*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
 1. The length of light-on since the begin.
 2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a[i]$ and $a[i+1]$ with time stamp $k \in (a[i], a[i+1])$, the total value of on-light will be total value of on light from the begin to $i$ + the total off-light from $a[i+1]$ till the end + the total on-light in the interval between $a[i]$ and a[i+1] after adding $k$ (Which is either $k - a[i]$ or $a[i+1] - k$ depending on the original status of the interval).
Summary, In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$