Java, Maximum Contiguous subsequence sum problem

In the first task, you are expected implement the three solutions for the maximum contiguous subsequence sum problem in the textbook (discussed in the class). The three solutions should be implemented in three separate java files (solution1.java, solution.java and solution 3.java). In each java file; 1. Implement a method public static int[] theMCSS(int (A) which accepts the input and returns an array which contains the start and end position of the maximum contiguous subsequence. Some sample inputs and return values of the function are shown below. Input Return Value {1,3,-5, 7, 4,-2) {-2, 11,-4, 13, -5, 2 => 20 -2,-5, -20,-5, -7} {3,4} {1,3} {-1,-1} 2. Write a method public static void testSolution to test your the MCSS method using some sample inputs and to assert that the correct output is given. Task 2: Analyzing the Performance Test and record the time takes by three solutions for different input sizes (at least for 10, 100, 1000, 10000) COMP 251: Data Structures and Algorithms - Lab 1 Page 1 of 2 For each input size, generate at least two testcases (two different inputs) For each testcase, run the program for at least three times and collect the time value and take the average of all the runs. Record the results in the following table (or a similar table). Solution 1 Solution 2 Solution 3 Input & Test Size 10 - Input 1 - Test 1 Size 10 - Input 1 - Test 2 Size 10 - Input 1 - Test 3 Size 10 - Input 1 Average Size 10 - Input 2 - Test 1 Size 10 - Input 2 - Test 2 Size 10 - Input 2 - Test 3 Size 10 - Input 2 - Average Size 10 - Average Size 100 - Input 1 - Test 1 Size 100 - Input 1 - Test 2 Size 100 - Input 1 - Test 3 Size 100 - Input 1 Average Size 100 - Input 2 - Test 1 Size 100 - Input 2 - Test 2 Size 100 - Input 2 - Test 3 Size 100 - Input 2 - Average Size 100 - Average Plot the results (average execution time against the input size) for three solutions in the same graph. Comment about any observations and interesting patterns. Submit your report as a pdf document