3. Prove the correctness of the rod cutting algorithm below using a loop invariant for the outer loop. Note that the algorithm's inputs are a table of rod prices and the length of rod to be cut, and its output is the optimal price that can be obtained from cutting the given length of rod. cut-rod (p, n) results = array of size n+1 results [0] = 0 for j1 through n m = p[j] for i 1 through j p[i] + results [j - i] r = if r> m: m = r results [j] = m return results [n]