4.(20 points)LetA[1n] be an (unsorted) array of n elements. We assume that no two elements of A are equal. We are also given another numberM. The problem is to find the largest element x in A such that the sum of the elements of A less than x is at mostM(i.e.,aA,a

Design anO(n) time algorithm for the problem.Hint:Use the prune-and-search technique.Note:You must describe the main idea of your algorithm (you may also give the pseudocode instead if it clearly explains the main idea) and analyze the time complexity