1. Write a C/C++ program that implements the brute force solution to the max subarray problem in (n²).
2. As we did in class, analyze each line of your brute force solution and show that overall it is (n²).
3. Implement the recursive solution for the max subarray problem.
4. Implement Kadane's linear time algorithm (again, for the max subarray problem) based on the algorithm that we discussed in class.

You should have the following modules: main.cpp, bruteForce.cpp, recursive.cpp, and kadane.cpp. Their templates are below. Note that these use C++ references. Any function that uses references (to "return" multiple values) must initialize them.

---------------------------------------------------------------------------

// file : main.cpp // author: ... // desc. : this file contains code that exercises the functions: // bruteForce_n2, find_maximum_subarray, and kadane. // #include  extern void bruteForce_n2 ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ); extern void find_maximum_subarray ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ); //to make things simpler for kadane: extern void kadane ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ); using namespace std; //------------------------------------------- int main ( int argc, char* argv[] ) { ... return 0; }

---------------------------------------------------------------------------

// file : bruteForce.cpp // author: ... // desc. : this file contains brute force implementations for the max sub // array problem in N^2. // using namespace std; //-------------------------------------------------------- void bruteForce_n2 ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ) { ... }

---------------------------------------------------------------------------

// file : recursive.cpp // author: ... // desc. : this file contains the entry point (and helper functions) for // the recursive max subarray problem/solution. #include  using namespace std; //--------------------------------------------------------------------------- . . (insert helper function(s) here, if any. they should all be static.) . //------------------------------------------------------------- void find_maximum_subarray ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ) { find_maximum_subarray( A, 0, N - 1, bestStart, bestEnd, bestSum ); }

---------------------------------------------------------------------------

//file : kadane.cpp //author: ... //desc. : implementation of kadane's linear time max sub array algorithm. using namespace std; //---------------------------------------------------------- void kadane ( int A[], int N, int& bestStart, int& bestEnd, int& bestSum ) { ... }