Write a Java program that implements the divide-and-conquer algorithm for the Maximum SubArray problem. Your program should consist of a single Java class named MaxSubarray.java, and should be compilable with the simple command "javac MaxSubarray.java". Your program should take two command-line arguments: an input file and an output file. The first line of the input file will be an integer N, which represents the number of problem instances contained in the file. It will then be followed by the N instance specifications. The first line of the specification of each instance will be an integer M, that represents the size of the array in that instance. It will be followed by M lines, each containing an element of the array. For example, the following is a file that contains two problem instances consisting of the two arrays (6,-1,4) and (1,-1,0,2):

2

3

6

-1

4

4

1

-1

0

2

The output file created by your program should contain N lines, where the ith line consists of a single number representing the solution to the ith instance in the input file. For example, the solution to the instance (6,-1,4) is 9, and the solution to the instance (13,-7,0,2) is 13. Therefore, the correct output file would be:

9

13

You will find sample input and output files on Moodle.