n HINTS: Algorithm ? processing ? Use a loop to read each line of data from List.dat
Question:
n
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 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
reinstantiated).
?
Input File
Scanner fileScan = new Scanner (new File("srcList.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 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).
?
?
?Statistics The Art and Science of Learning from Data
ISBN: 978-0321755940
3rd edition
Authors: Alan Agresti, Christine A. Franklin