HINTS:

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 methodmore 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

reinstantiated).

Input File

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

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 this 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 well 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). Well 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).

Write a Java application, which uses recursion to find the maximal (largest) contiguous sum in a list of integers. Read from a text file (List.dat) lines of data where each line represents a list in this format: list-size 4 numbers in the list separated by blanks 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-1058 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. Output For each line of data read, display the largest sum of consecutive integers in the list followed by the list itself. For example, lists as above, your output would be: Largest Sum 1033 100 3700 103 100 Used List 2-4 30 15 -7 -5 1000 -50 100 1000 -2000 900 2800 -2900 2801 100-10 5 8 100-50 5 8