Assignment 4 Fibre Cabling

Requirements
This fourth assignment lets you get familiar with successive improvements with algorithm design for a concrete “real-world” problem. There are three programs required using cleaver brute-force, divideand-conquer and dynamic programming. It is worth 5% of your total course marks. Please try and test with your own generated input cases before submitting to the automated marker.
Problem: Fibre Cabling
A big internet infrastructure company in New Zealand has been tasked with wiring up homes with fibre optic broadband cables. However, since this is a business for profit, not all homes will need to be hooked up. The company Circus has asked you to help them determine which homes they should connect cables, ready for sale. The main constraint of this problem is that if two homes on a street is cabled then all intermediate homes on the path between them must also be, irrespective if they signup for an internet plan or not. The company makes a certain amount of profit based on which plan customers purchase; it also losses money if a complicated connection is done without any plan purchase. An input scenario is a sequence a1,a2,...,an of n ≤ 100000 integers on one line, denoting the profit/loss for connecting each house on a street of length n. The entry at position i, 1 ≤ i ≤ n, is positive for profit and negative for loss. We have many streets of data to process and a single line containing only one integer denotes the end of input (this scenario is not processed). We can assume each scenario has at least one positive house value ai, since otherwise Circus would not even consider cabling that street.
The output of your program, one line per each scenario, is the maximum profit obtainable for that street.
Sample Input:
10 -4 5 3 -4 5 3 -10 4 41 -1 10 0 20 -4 -3 8 -7 4 4 4 -3 1 0 0 -4 1 3 -4 7 -2 -2 3 1
Sample Output
11 5 45 31 9
1
Submission 1: fibreBrute.ext
There is a natural simple brute-force algorithm that tries and sums every subsequence ai + ai+1 + ai+2 +···+ aj−1 + aj for 1 ≤ i ≤ j ≤ n. Then return the maximum of all combinations of starting positions i and ending positions j This algorithm has running time O(n3). With a simple observation that, one can compute both the sums ai +···+ aj+1 and ai+1 +···+ aj from ai +···+ aj with one addition/subtraction, we can get a O(n2) algorithm. An implementation of this algorithm is required for a program named fibreBrute.ext, where ext is an extension of the programming language of your choice.
Submission 2: fibreDC.ext
For this part of the assignment we want to develop an even higher performance algorithm based on the divide-and-conquer design approach. An O(nlgn) algorithm is possible by using an algorithm similar to the ‘counting inversions’ algorithm given in lectures. Consider the following sequence:
a1,a2,...,an 2−1,an/2,an 2 +1,...,an−1,an
An optimal solution either uses the element an/2 or not. So we can take the maximum of three cases: recursively solve subproblem a1,...,an 2−1, recursively solve subproblem an 2 +1,...,an, or the “conquer” case that includes an/2. Submit a program named fibreDC.ext.
Submission 3: fibreDP.ext
Finally we want to improve to an O(n) time algorithm. You should use dynamic programming to solve this case. Submit a problem named fibreDP.ext.