The input to this problem is an array A$[$l$..$n$]$ of real numbers. You need to find out what the highest value is that can be obtained by summing up all numbers of a contiguous subsequence A$[$i$],$ A$[$i $+1],...$ A$[$j$]$ of A$.$ If A does not contain negative numbers, the problem is trivial and can be solved by summing up all the elements of A$.$ It becomes more tricky when A contains a mix of positive and negative numbers though. For instance, for A $=[2,11,4,13,5,3],$ the solution is $20(114+1320).$ For A $[2,1,3,4,1,2,1,5,4],$ the solution is $6(4-1+2+1=6).$ The sum of the numbers of an empty subsequence is $0.$ There exists a brute force solution that solves this problem in O$($n $3),$ but it is also possible to solve the problem in linear time. In this problem, you are asked to design a dynamic programming algorithm that solves the problem described above in linear time. $($a$)$ Characterize the structure of an optimal solution. Show how you would decompose the solution into sub$-$problems and recursively define the optimal solution by expressing it in terms of optimal solutions for smaller problems. State and define all your notations for full credit. $($b$)$ Present your algorithm in pseudocode. $($c$)$ Briefly explain how and why your algorithm works. $($d$)$ Give a brief explanation of why your algorithm indeed runs in linear time.