You$$re headed to a one$-$entry, one$-$exit music festival. To optimize your experience, you$$ve organized an array of bands in the order they$$re playing, with the exact values in the array being every band$$s utility value indicating how much enjoyment you$$ll derive. Your goal is to enter and exit strategically to maximize your overall enjoyment. This is the problem of maximizing the sum of a contiguous sub$-$array within a given array.

It$$s called the maximum subsequence sum problem. If all values in the array are negative, the maximum subsequence sum is $0.$

Input: Given an array A of integers.

Process: Write an algorithm max$\_$sub$\_$sum$($A$),$ which traverses A to find the maximum subsequence sum.

Output: The value of the maximum subsequence sum in A$.$

For ex:

A $=[2,11,4,13,5,2]$

max$\_$sub$\_$sum$($A$)=20($obtained from A$[1.\mathrm{.}3])$

Note: Your algorithm can take any number of operations to compute this, i$.$e$.$ any time complexity will be accepted. Derive an O$($n$)$ solution for this question which includes the algorithms, appropriate proofs of correctness, time$-$space

complexity analysis.