The Maximum-Sum Monotone Sub-Array Problem: Input: An array A[1..n] of arbitrary positive integers. Output: The maximum-element-sum contiguous sub-array of A[1..n] whose entries form a monotone sequence (either ascending or descending)

[Hint: Use an incremental approach. Note: ascending means non-decreasing and descending means non-increasing. Follow the Loop-Invariant design-&-verification method for iterative algorithms, and the strong induction method for recursive algorithms]