Your report must be typed and submitted online. Each team member's name must be listed as well as any resources used to finish the project. For this project, you will design, implement and analyze (both experimentally and mathematically) four algorithms for the maximum subarray problem: Given an array of small integers All,...,n], compute max YK- A[k], and determine the subarray For example, MAXSUBARRAY( 131, -41, 59, 26, -53, 58, 97, -93, -23, 84]) 187 with sulbarray J 59, 26, 53, 58, 97 Note: If there are multiple subarrays with the same sum you only need to identify one Instructions You may use any language you choose to implement your algorithms. All algorithms will take as input an array and output the subarray with a maximum sum along with the sum. Your algorithms are to be based on these ideas: Algorithm 1: Enumeration. Loop over each pair of indices i, f and compute the sum Alk]. Keep the best sum you have found so far Algorithm 2: Better Enumeration. Notice that in the previous algorithm the same sum is computed many times In particular, notice that A[k]can be computed from j-1 A[k] in O(1) time, rather than starting from scratch. Write a new version of the first algorithm that takes advantage of this observation Algorithm 3: Divide and Conquer. If we split the array into two halves, we know that the maximum sulbarray will either b Contained entirely in the first half Contained entirely in the second half or Made of a suffix of the first half of the subarray and a prefix of the second half Algorithm 4: Linear-time. Use the following ideas to develop a nonrecursive linear time algorithm. Start at the left end of the array and progress towards the right, keeping track ofthe maximum subarray sum seen so far. Knowing a maximum subarray of AI1.. jl, extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of 1] is either a maximum subarray of A[1.. J] or a subarray Ali j+11, for some 1 s is j+1. Determine a maximum sulbarray of the form Ali.. j 1] in constant time based on knowing a maximum subarray ending at index j Your report must be typed and submitted online. Each team member's name must be listed as well as any resources used to finish the project. For this project, you will design, implement and analyze (both experimentally and mathematically) four algorithms for the maximum subarray problem: Given an array of small integers All,...,n], compute max YK- A[k], and determine the subarray For example, MAXSUBARRAY( 131, -41, 59, 26, -53, 58, 97, -93, -23, 84]) 187 with sulbarray J 59, 26, 53, 58, 97 Note: If there are multiple subarrays with the same sum you only need to identify one Instructions You may use any language you choose to implement your algorithms. All algorithms will take as input an array and output the subarray with a maximum sum along with the sum. Your algorithms are to be based on these ideas: Algorithm 1: Enumeration. Loop over each pair of indices i, f and compute the sum Alk]. Keep the best sum you have found so far Algorithm 2: Better Enumeration. Notice that in the previous algorithm the same sum is computed many times In particular, notice that A[k]can be computed from j-1 A[k] in O(1) time, rather than starting from scratch. Write a new version of the first algorithm that takes advantage of this observation Algorithm 3: Divide and Conquer. If we split the array into two halves, we know that the maximum sulbarray will either b Contained entirely in the first half Contained entirely in the second half or Made of a suffix of the first half of the subarray and a prefix of the second half Algorithm 4: Linear-time. Use the following ideas to develop a nonrecursive linear time algorithm. Start at the left end of the array and progress towards the right, keeping track ofthe maximum subarray sum seen so far. Knowing a maximum subarray of AI1.. jl, extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of 1] is either a maximum subarray of A[1.. J] or a subarray Ali j+11, for some 1 s is j+1. Determine a maximum sulbarray of the form Ali.. j 1] in constant time based on knowing a maximum subarray ending at index j