This pseudo-code seems to be with only one pass no ? Can someone find a counter-example ?
overall_max=0
index_of_overall_max=0
Second_max=0
index_of_second_max=0
Array_of_cumulated_Sum=0
Total=0
for i from left to right
if Height(i)>overall_max
//Water Area between new max and old max
Total+=overall_max*(i-index_of_overall_max+1)-(Array_of_cumulated_Sum(i)-Array_of_cumulated_Sum(index_of_overall_max))
overall_max=Height(i);
index_of_overall_max=i;
Second_max=0;
index_second_max=i+1;
else
if Height(i)>Second_max
//All the parts on second max is only to not miss the kept water at the end between the overall_max and another local max
Second_max=Height(i);
index_second_max=i
end
end if
Array_of_cumulated_Sum(i)=Array_of_cumulated_Sum(i-1)+Height(i)
end for
//At the end : water area between second max and overall max
Total += Second_max*(index_of_second_max-index_of_overall_max+1)-(Array_of_cumulated_Sum(index_of_second_max)-Array_of_cumulated_Sum(index_of_overall_max))
return Total