Hacker News new | ask | show | jobs
by JavascriptMan 4612 days ago
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