Divide & Conquer and Dynamic Programming algorithms. Using JAVA

The goals of this project are:  To design Divide & Conquer and Dynamic Programming algorithms for a given problem.  To prove the correctness of your algorithms and analyze them in terms of running time and space requirements.  To implement and test them.  To document your findings in a project report. You are organizing the perfect party and you are given a list of people that can potentially attend the party. Each person in the list is assigned a positive integer (between 1‐1000) 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, you need to come up with two algorithms (a Divide & Conquer algorithm and a Dynamic Programming one) that return the maximum sum achieved as well as the people to attend the party, subject to the constraint mentioned above. For example if the list of ratings is 7, 3, 5, 8, 2, 1, 2, 3, then the best sum is 19, achieved by the underlined people. You should implement the two algorithms, test them for correctness using the test instances that can be found in the class web page and evaluate their performance. 3. Project Implementation You can work in teams of up to two. The teams are expected to accomplice the following goals.  Implement your algorithms in JAVA following the conventions below: o Classname: Party o Method signature: int partySum (int[] rating) (your method should be public) o rating[] is a 1‐dimensional array of maximum size 10000 containing the rating of each person o The ratings are integers in the range 1‐1000 o When your method is called, it should print the maximum sum attained as well as the people that will attend the party. o Example: partySum[7, 3, 5, 8, 2, 1, 2, 3]. Your method should print Maximum sum: 19 The following persons should attend the party: 0, 3, 5, 7  Add comments to your code. At least 20% of your source code must be in the form of valid and informative comments.  Your methods should compile with no mistakes. They will be tested on bigger and more complex examples, so make sure your algorithms work correctly.  You need to submit a clearly written project report detailing all your work including all the steps of the design process (problem formulation, D&C and DP algorithm descriptions, analysis of running time and space requirements), screenshots of your program execution with specific examples, and conclusions.  The report should be professionally written using a text processing software (e.g., MS Word or other), and all figures, tables, etc. should also be generated preferably using some software tool.