Consider the max-sum problem: Given an array A of size n containing positive and negative integers, determine indices i and j, 1 <= i <= j <= n, such that A[i] + A[i + 1] + ... + A[j] is a maximum. Give an O(n) time dynamic programming algorithm for the problem. Give the recursive formulation, clearly explaining your notation and also write the pseudocode of the DP (iterative) algorithm.