In a street with n houses, Santa Claus can deliver presents to a consecutive subinterval of houses. The elves have prepared an array A[1n] where A[i] indicates how the kid in the i-th house has behaved in the last year (both positive and negative integer scores are possible). In order to select which houses to visit, Santa now wants to know what is best total score among all subintervals, max1i,jnk=ijA[k] a. Help him and design an algorithm running in time O(n). Hint: Compute for each index j what is the optimal subinterval sum of an interval ending at j. b. In reality, Santa has to visit a whole city which we model as an nn grid of houses, and he is allowed to visit any square subgrid. Again, the elves have prepared a two-dimensional array A[1..n,1n] where A[i1,i2] indicates how the kid in the (i1,i2)-th house has behaved. Help him and compute max1i1,j1nmax1i2,j2nk1=i1j1k2=i2j2A[k1,k2]. The number of points awarded to your solution depends on the running time of your algorithm. Figure 3: An example of Exercise 3b. The highlighted region is the best-possible subsquare [i1..j1][i2j2] with entry sum 35