Question

Please provide a detailed walk through osf this Java application, which uses recursion to find the maximal (largest) contiguous sum in a list of integers. 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., NO empty list. No error checking needed. 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 implement 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)

Answer 1

now we solve the given question by using Kadane’s Algorithm.

first we know about Kadane’s Algorithm.

Kadane's Algorithm in Java. Kadane's Algorithm to solve maximum sum subarray problem.

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Lets see what is expected output from given input,

Case 1:
        Input:
            {3, -1, -1, -1, -1, -1, 2, 0, 0, 0}
        Output:
            start index :0
            End index :0
            Sum :3
           
Case 2:   
        Input:      
            {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}
        Output:      
            start index :3
            End index :8
            Sum :17

Case 3:
        Input:  
            {-2,-3,4,-1,-2,1,5,-3}
        Output:
            start index :2
            End index :6
            Sum :7

Case 4:
        Input:  
            {-1,3,-5,4,6,-1,2,-7,13,-3}
        Output:
            start index :3
            End index :8
            Sum :17

Case 5:
        Input:  
            {-1}
        Output:
            start index :0
            End index :0
            Sum :-1

Case 6:
        Input:  
            {-6,-2,-3,-4,-1,-5,-5}
        Output:
            start index :4
            End index :4
            Sum :-1

by using this method

now we solve the given question.

first we take examples like   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.

know we perform th Largest sum of The list used consecutive int items. by using Kadane's Algorithm.

the given below is the code for perform Largest sum of The list used consecutive int data items. by using java language.

import java.io.*;
// Java program to print largest contiguous array sum
import java.util.*;

class Kadane
{
   public static void main (String[] args)
   {
       int [] a = {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};
       System.out.println("Maximum contiguous sum is " +
                                   maxSubArraySum(a));
   }

   static int maxSubArraySum(int a[])
   {
       int size = a.length;
       int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

       for (int i = 0; i < size; i++)
       {
           max_ending_here = max_ending_here + a[i];
           if (max_so_far < max_ending_here)
               max_so_far = max_ending_here;
           if (max_ending_here < 0)
               max_ending_here = 0;
       }
       return max_so_far;
   }
}

we run this code and we get the largest sum of integers value...

we have another method to find out the largest integer value by given int data items.

the another method is called dynamic programming.

Algorithmic Paradigm: Dynamic Programming

Following is another simple implementation suggested by Kumar. The implementation handles the case when all numbers in array are negative.

the given below code will use you got a output.

// Java program to print largest contiguous
// array sum
import java.io.*;

class GFG {

   static int maxSubArraySum(int a[], int size)
   {
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
       curr_max = Math.max(a[i], curr_max+a[i]);
       max_so_far = Math.max(max_so_far, curr_max);
   }
   return max_so_far;
   }

   /* Driver program to test maxSubArraySum */
   public static void main(String[] args)
   {
   int a[] = {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};
   int n = a.length;
   int max_sum = maxSubArraySum(a, n);
   System.out.println("Maximum contiguous sum is "
                   + max_sum);
   }
}

// This code is contributd by manikanta immidi.

//Please ask any more doubts.