Being the chief climatologist of your city, you have been given the rainfall data for each day for the last 100 years in your city. So you have an array R [1 ..n ] where R [ i ] lists the amount of rain measured in your city on the i th day (from some starting point). Let = ( 1 i n R [ i ]) /n denote the average rainfall in R . For an interval I = [ l,r ], 1 l,r n of days, we define the deficit of I to be ( r l+ 1) ( l i r R [ i ]). That is, the deficit of I is the difference between the total amount of rain expected in I and the total amount of rain that actually fell in I . (Note that the deficit of an interval can be negative.) For a new climate study, you have been asked to find an interval I that has the largest deficit.

Design a brute-force (n2) time algorithm for your problem.

Also a better algorithm