Part A :

1) Implement both the Brute Force and Improved versions of the MCS algorithms.

2) Checkthe correctness of the algorithms for the following sequences:

1. -1, -2, -3, -4, -5, -6

2. -1,1,-1,1,-1,1

3. -1,2,3,-3,2

4. 1,-5,2,-1,3

5. -2,2,-2,-2,3,2

6. Modify both algorithms to record the number of iterations used. Test your modified algorithms on the above examples.

7. Generate 10 random sequences of length 5, 10, 15, ..., 50 each (100 sequences in totals). Record the number of iterations for each sequence. Plot the results (x=length = n, y=iterations) to compare the algorithms time complexity. Also compare the Brute Force algorithms iterations with n(n+1)/2 and the Improved algorithms iterations with n. [Produce 3 plots: Brute vs. Improved, Brute vs. n(n+1)/2 and Improved vs. n].