THIS QUESTION MUST BE ANSWERED WITH CLEAR ENGLISH PSEUDOCODE!

4. You are playing a game on an n n grid of cells. Each cell contains a single integer: the cell in row r, column c contains the integer A[r][c], where A[1..n][1..n] is a two- dimensional array of integers. You start at the top-left cell (1, 1) and will move to the bottom-right cell (n, n). At each step, you can only move to the cell immediately below or to the right. Specifically, from cell (r,c) you can move to (r + 1,c) or (rc+ 1) only. Your score is equal to the sum of the integers among all cells vou have passed through: vou would like to maximise this score. 1. (a) Give an O(n-) algorithm that computes the maximum possible score. 2 Describe how to extend your algorithm from part (a) to also output any path (b) that produces this maximum possible score. This path should be output as a series of D (down) and R moves, for instance DDRDRR is a valid path on a 4x4 grid. The overall time complexity of the algorithm should still be O (n-) 2 3. (c) Suppose as input you are given the array A[1.n][1..n] in read- only memory This means that you can freely read its values, but cannot modify it in any way. Design an algorithm that runs in O(n-) time that outputs any path with maximum possible score, just as in part (b). However, your algorithm may only use O(nvn) additional memory on top of the input array. This additional memory can be freely read from or written to