Use the following ideas to develop a nonrecursive, 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$ by using the following observation: a maximum subarray of $A[1...j+1]$ is either a maximum subarray of $A[1...j]$ or a subarray $A[1...j+1]$, for some $1\leq i\leq j+1$. Determine a maximum subarray of the form $A[i...j+1]$ inconstant time based on knowing a maximum subarray ending at index $j .$
