A segment of an input sequence is a subsequence whose members occur consecutively in the input. A segment can be referred to by the first and last index of its elements, since no elements between these indices will be left out. For example, if the input sequence is 1, -2, 5, 4 -3, then 1, -2 is a segment; 5, 4, -3 is a segment; but -2, 5, -3 is not a segment. Design an efficient dynamic programming algorithm to find the segment of an input sequence A (of length n) that has the maximum sum. Note that the input numbers can be negative. Your algorithm should find both the segment and its sum. You are trying to compute: max_1 lessthanorequalto i lessthanorequalto j lessthanorequalto n (sigma^j _k=i A[k]) where A is the input sequence of real numbers