Problem $1$: Max Subarray Problem

Recall the max subarray problem presented in class. We used divide and conquer method to derive a $\backslash$Theta $($log$())$

worst case time algorithm to solve it$.$

In this assignment, we would like you to solve this problem in $\backslash$Theta $()$

time. I.e$,$ your algorithm should be able to compute the result by just iterating through the array and keeping track of some quantities.

Let $[$a$0,$ a$1,....,$ak$]$ be a python array $($list$)$ of size k $+1.$ Here is the idea: