Suppose you are given an array A[1 . . . n] of numbers, which may be positive, negative,or zero. Describe and analyze an algorithm (with best possible worst case running time) that finds the largest product of elements in a contiguous subarray A[i . . . j].For example, given the array [6, 12, 7, 0, 14, 7, 5] as input, your algorithm should return 504 (product of first 3 numbers). Given the one-element array [3] as input, your algorithm should return 1 (product of elements in an empty set is considered to be 1). ( 5: depending on the running time)