Write a Java application, which uses recursion to find the maximal (largest) contiguous sum in a list of integers.. Please base code on the algorithm below.

Input Read from a text file (List.dat) lines of data where each line represents a list in this format:

list-size    numbers in the list separated by blanks 4           100 -50 5 8

For example, List.dat might contain: 7     -2    -4    30     15     -7     -5     1000 2   -50   100 6   1000   -2000    900    2800    -2900     2801 0    4   100    -10   5    8 4   100    -50    5    8

Note: the list-size must be greater than 0. Bypass any line with 0 or a negative number as the first number, i.e., do NOT create an empty list. You do NOT have to do any error checking. You may assume that your input file is structured correctly: it contains all integers, and if the first number on a line is n, then there are n integers that follow it on that line.

Output For each line of data read, display the largest sum of consecutive integers in the list followed by the list itself. For the example lists as above, your output would be:

Largest sum of The list used consecutive integers 1033   -2     -4     30     15     -7     -5     1000 100    -50     100 3700   1000     -2000     900     2800     -2900    2801 103    100     -10     5     8 100    100     -50     5     8

Algorithm - processing

• Use a loop to read each line of data from List.dat until end-of-file is reached
• On each pass of the loop create an array of list-size (1st number on the line) to hold the list of numbers read (from the rest of the line)
• Invoke a recursive method (or a surrogate/helper method that invokes a recursive method— more on this below) that returns the largest contiguous sum for this list
• Display the sum and the list (as above) • Do not use any “global” variables in your code (your methods should use only parameters or local variables, no static variables that recursive methods would refer to, as they would not be instantiated)

Input File Include a file of test data in your src folder. The contents of your file will be replaced with my test data. Recall you can access this file in your program with this code:

Scanner fileScan = new Scanner (new File("src\\List.dat"));

You can recall in CSC 135 we read from a file that contained URLs.

Using Recursion Your main method should call this helper method, which returns the maximum contiguous sum on the list aList:

//This method returns the maximum contiguous sum   public static int maxSum(int[] aList)

but in order to use recursion we need more parameters, so the method above maxSum will simply serve as a surrogate which calls another method, the recursive method, which does all the work:

//This method returns the maximum contiguous sum from a list stored in an //array which begins at cell “start” and ends at cell “end” public static int maxContigSum (int[] aList, int start, int end)

Using the approach for developing a recursive solution:

• Base case: a list with 1 item. What will the maximum sum be? 
• Assume we can determine the maximum sum for a list of contiguous items in a shorter list. (Looking ahead: the shorter list that we’ll use in the next step, the general case, will be the list beginning at cell “start+1” and ending at cell “end (you could also do “start” till “end-1”). We’ll remember that sum as it will be a candidate for the maximum sum that our method should return. 
• General case: From our assumption we know what the maximum contiguous sum is for all cells excluding the first cell, so now we need to consider any sum, which contains the first cell. So now compute (use a loop, not recursion here) all possible sums from your list that include the first cell. As you compute these sums compare them to your maximum sum so far (which initially will be what was returned by your assumption above).