Algorithms and Their Analysis:

Question 8 (1 credit) In fact, we can do better than the divide-and-conquer approach for the maximum subarray problem. User the following ideas to develop a non-recursive, linear-time algorithm for the maximum subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j], extend the answer to find a maximum subarray ending at index j +1 using the following observation: a maximum subarray of A[i..j +1] is either a maximum subarray of A[1..j] or a subarray A[i..j +1], for some 1 S isj+1. Finding a maximum subarray of A[i..j + 1] can be done in constant time, because we already know the maximum subarray of A[1.. Please write down the pseudocode