PLEASE SOLVE QUESTION (f) with these instances test using C code

You are organizing the perfect party and you are given a list A of people that can potentially attend the party. Each person in the list is assigned a positive integer (between 1-100) that rates how much this person can contribute to the success of the party. However, the list is organized in such a way such that if you select the i-th person from the list to attend the party then you cannot select any of its neighbors because they do not mix well with each other. So, given the list and the ratings of the people, come up with a Divide & Conquer algorithm that returns the maximum sum achieved by people that can attend, subject to the constraint mentioned above. For example if the list of ratings is 7, 3, 5, 8, 2, 1, 2, 3, th the best sum is 19, achieved by the underlined numbers. (a) (3 points) Suppose you divide the list into parts L, R of size n/2 (assume n is a power of 2) and you compute best sum of ratings that can be achieved recursively for each part. Then simply return the sum of these numbe Does this solve the problem? Explain why or why not. Now present your own D&C approach, again splitting the input in half. you need to: (b) Give a high level description of your algorithm. (C) Show how you handle the base cases. (d) Explain carefully why your algorithm is correct. Justify the recurrence T(n) of its running time and solve it using any method we learned in class. (f) Implement your algorithm and run it on the test instances shown in the web page. Sh screenshots of its execution. Hint: Your D&C algorithm should return additional values. The running time should be linear, given by the expressi T(n) = 2T(n/2) + O(1). , Test your algorithm with the following instances: = N=10 A[] = {6, 8, 2, 6, 18, 6, 3,1,4,10} Best sum is 31 N-22 A[] = 19, 18, 6, 7,5, 8, 1, 16,17,6,16, 5, 20, 3,6,7,3, 2, 1, 19 Best sum is 125 N-8 AI] = 8,8,28, 9,42, 22,12, 100, 56, 2,74,12,23,81,99,47,40,49,9 1,2,3,6,6,7,6,74,56,59,2,34} Best sum is 884 A[] = 9,8,82,58,64,69,27,76,96,21,85,4,13,96,92,60,42,67,84 ,52, 3, 2, 9, 5,3,2,14,3,29, 20,98,88,73,72,35,26,53,1,89, 3 9,24,8,9,47,4,67,8,74,76,83} Best sum is 1559 18 A[] = {4,8,27,53,45,100,28,41,8,39,95,27,70,93,77,9,42,9,18, 38, 2,78,26,43,17,22,57,57, 3,65,52, 94,11,30,90, 57,98,25,43,2 3,61,94,67,8,25,3,74,77,24,39,15,15,35,6,67,43,53,36,6,40 ,71,19,5,8,82,52,6,92,25,1,57,16,52, 25, 28,21,39,62,62,98, 55,74,16,29,9,66,41,51,17,26,93,86,14,9,45,63,35,51,13, 100} Best sum is 2915