CIS-5050 Homework #1: Maximum Subarray

Due: Friday, September 3, 2021

Read Chapter 2 in the text. Take note of the pseudocode for InsertionSort and MergeSort.

Download and install the GNAT Community 2021 Ada compiler from AdaCore.
Clone the GitHub repository that contains the homework starter files. You will be building on this project throughout the course by adding new files to it in both this and in future homework assignments. The project's configuration is controlled by the cis5050.gpr project file. You can either open this project in the GNAT Studio integrated development environment or use it as a command line argument with the gprbuild command line tool. See the README.md file contained in the archive for more information.

The starter archive contains examples of InsertionSort and MergeSort in Ada, as translated from the pseudocode in the text. It also includes some tests for those algorithms. All the tests should pass. Be sure you can compile the test program (tests.adb) and execute it.
In Chapter 4 of the text, review section 4.1 on the maximum subarray problem. That section describes a recursive algorithm to solve the problem and also shows a sample problem instance to help explain the problem. Your assignment is to implement the pseudocode for the two functions Find_Max_Crossing_Subarray and Find_Maximum_Subarray. I recommend creating a local branch in your Git repository for each assignment you do. This will minimize the chance of creating a conflict when you update the main branch with additional files from me.

The pseudocode makes use of tuple types. Ada does not have tuple types, but you can simulate them using Ada records. For example:
```
        type Subarray_Summary is
           record
              Low_Index  : Positive;
              High_Index : Positive;
              Sum        : Element_Type;
           end record;
      
```
You can then declare the functions, for example, like this:
```
        function Find_Maximum_Subarray
          (A : Array_Type; Low, High : Positive) return Subarray_Summary
        with Pre => (Low <= High);
      
```
Note that for this to work, the entire package must be generic and not just the procedure inside that package (This is because a generic type is being used in the definition of Subarray_Summary. To declare a generic package, put the generic header immediately before the package CIS5050.Arrays is... line in the specification file.

Finally, this algorithm assumes the elements of the array are integers that can be added together (with both positive and negative values). Using the generic parameter declaration of Element_Type is private is too general; such a declaration does not require Element_Type to be anything like an integer. To deal with this, declare the generic parameter this way:
```
        type Element_Type is range <>;
      
```
This will require the actual parameter to be some kind of signed integer. This also means you can use integer operations on variables of type Element_Type, like integer addition, etc., inside the generic body (without tediously declaring the necessary operations in the generic header).

The pseudocode also uses downto to describe a loop that iterates backwards over its range. In Ada, you use in reverse to do this:
```
        for I in reverse 1 .. 10 loop
      
```
Notice that the range is still specified in forward order as 1 .. 10. In Ada ranges like 10 .. 1 are actually considered empty ranges containing no values at all!

Submit only your modified cis5050-arrays.adb file to Canvas.