import java.util.Scanner;
import java.util.Random;
import java.util.Arrays;

/* Java application that includes a recursive method for computing the
** maximum segment sum of an array of integers.
**
** The purpose of this class is to illustrate a particular asymptotic
** growth rate in running time.
**
** Author: R. McCloskey
** Date: April 2025
*/


public class MaxSegSum_S25 {

   // input variables 
   // ---------------

   private static int randSeed;   // These variables are "global" 
   private static int arrayLen;   // for the convenience of using
   private static int minVal;     // them in both main() and getInputs()
   private static int maxVal;
   private static Scanner keyboard;


   // instance variables
   // ------------------

   private int callCntr;
   private int callDepth; 
   private int maxCallDepth; 


   // methods that (recursively) sum the elements of a specified array segment
   // ------------------------------------------------------------------------

   /* Returns the maximum among the sums of the segments in the given array.
   */
   public int maxSegSumA(int[] ary) { 
      return maxSegSumA(ary, 0, ary.length);
   }

   /* Returns the maximum among the sums of the subsegments of the given
   ** array segment.
   ** pre: 0 <= low <= high <= a.length
   */
   public int maxSegSumA(int[] ary, int low, int high) {
      entering();
      int result;
      if (low == high) { 
         // The only subsegment of an empty segment is itself,
         // and the sum of its elements is zero
         result = 0;
      }
      else {
         // The subsegments of a[low..high) can be partitioned into
         // those that are prefixes of a[low..high) and those that 
         // are not.  
         result = Math.max(maxPrefixSum(ary, low, high),
                           maxSegSumA(ary, low+1, high));
      }
      leaving();
      return result;
   }

   /* Returns the maximum among the sums of the prefixes of the given
   ** array segment.  A prefix of a segment is a sub-segment that is either
   ** empty or else includes the first element of the former.  For example,
   ** the prefixes of a[4..8) (in increasing order of length) are a[4..4) 
   ** (which is empty), a[4..5), a[4..6), a[4..7), and a[4..8).
   ** pre: 0 <= low <= high <= a.length
   */
   public int maxPrefixSum(int[] a, int low, int high) {
      entering();
      int result;
      if (low == high) {   // a[low..high) is empty
         // The only prefix of an empty segment is itself empty,
         // and the sum of its elements is zero.
         result = 0;
      }
      else {  // a[low..high) is not empty
         // The maximum sum among any prefix of a[low..high) is a[low]
         // added to the maximum sum among the prefixes of a[low+1..high),
         // unless a[low] is "so negative" as to make that value itself negative,
         // in which case the empty prefix of a[low..high) has the maximum
         // sum (namely, zero).
         int m = maxPrefixSum(a, low+1, high);
         result = Math.max(0, a[low] + m);
      }
      leaving();
      return result;
   }


   // methods that pertain to the call and depth counters 
   // ---------------------------------------------------

   public int callCount() { return callCntr; }

   public void resetCallCount() { callCntr = 0; }

   public int maxCallDepth() { return maxCallDepth; }

   public void resetDepth() { 
      callDepth = 0;
      maxCallDepth = 0;
   }

   /* In response to entering a recursive method, updates the global variables
   ** keeping track of the # of such calls made, the current depth of recursion,
   ** and the max depth reached (since reset() was called).
   */
   private void entering() {
      callCntr++;
      callDepth++;
      if (callDepth > maxCallDepth)
         { maxCallDepth = callDepth; }
   }


   /* In response to leaving a recursive method, updates the global variable
   ** keeping track of the current depth of recursion,
   */
   private void leaving() { callDepth--; }


   // main method (for testing purposes)
   // ----------------------------------

   public static void main(String[] args) {
      System.out.println("Welcome to the Recursive Max Segment Sum Program!");
      MaxSegSum mss = new MaxSegSum();
      keyboard = new Scanner(System.in);
      getInputs();
      while (arrayLen >= 0) {
         int[] ary = randomArray(arrayLen, randSeed, minVal, maxVal);
         System.out.printf("Computing maximum segment sum of array\n");
         displayArray(ary); 
         int resultA = performTest(mss, 'A', ary);
         //int resultB = performTest(mss, 'B', ary);
         //if (resultA != resultB) {
         //   System.out.println("** ERROR: maxSegSumA() and maxSegSumB() " +
         //                      "produced different results!");
         //}

         getInputs();
      }
      System.out.println("\nGoodbye.");
   }

   private static void displayArray(int[] a) {
      final int LINE_WIDTH = 75;
      final char COMMA = ',';
      String arrayImage = Arrays.toString(a);
      final int N = arrayImage.length();
      int pos = 0;
      while (pos != N) {
         if (pos + LINE_WIDTH >= N) {
            System.out.println(arrayImage.substring(pos));
            pos = N;
         }
         else {
            int endPos = arrayImage.indexOf(COMMA, pos+LINE_WIDTH) + 1;
            if (endPos == 0) {  // unusual case
               System.out.println(arrayImage.substring(pos));
               pos = N;
            }
            else {
               System.out.println(arrayImage.substring(pos, endPos));
               pos = endPos;
            }
         }
      }
      System.out.println();
   }


   /* Uses the given MaxSegSum object to compute the maximum of the sums 
   ** of the segments of the given array, using either maxSegSumA() or 
   ** maxSegSumB() according to the value of 'whichMethod'.  Then reports 
   ** the results and returns the computed vaule to the caller.
   */
   private static int performTest(MaxSegSum mss, char whichMethod, int[] a) {
      mss.resetCallCount();
      mss.resetDepth();
      int maximumSum;
      //if (whichMethod == 'A')
      { maximumSum = mss.maxSegSumA(a); } 
      //else  // use method B 
      //   { maximumSum = mss.maxSegSumB(a); } 

      System.out.printf("\nmaxSegSum%c():\n", whichMethod);
      System.out.printf("  applied to array of length %d\n", a.length);
      System.out.printf("  reported max segment sum: %d\n", maximumSum);
      System.out.printf("  call count: %d\n", mss.callCount());
      System.out.printf("  max depth of recursion: %d\n", mss.maxCallDepth());
      /*
        System.out.printf("maxSegSum%c() used %d calls to a max depth of %d " +
                          "to compute sum %d of an array of length %d\n",
                          whichMethod, mss.callCount(), mss.maxCallDepth(), 
                          maximumSum, a.length);
      */
      return maximumSum;
   }


   /* Using an instance of the Random class (initialized using the given
   ** seed), creates, fills, and returns an array of the specified length
   ** containing "random" values in the specified range (minVal..maxVal).
   ** pre: len >= 0, minVal <= maxVal
   */
   private static int[] randomArray(int len, int seed, int minVal, int maxVal) {
      int[] result = new int[len];
      Random rand = new Random(seed);
      int minMaxDelta = maxVal - minVal + 1;
      for (int i=0; i != result.length; i++) {
         result[i] = minVal + rand.nextInt(minMaxDelta);
      }
      return result;
   }

   /* Prompts the user for each of four inputs and places the responses
   ** in the corresponding global variables.
   */
   private static void getInputs() {
      String lengthPrompt = "\nEnter desired array length (negative to quit): ";
      String seedPrompt = "Enter integer to be used as seed for Random object:";
      String minValPrompt = "Enter minimum possible array element value: ";
      String maxValPrompt = "Enter maximum possible array element value: ";

      arrayLen = readInt(keyboard, lengthPrompt);
      if (arrayLen >= 0) {      
         randSeed = readInt(keyboard, seedPrompt);
         minVal = readInt(keyboard, minValPrompt);
         maxVal = readInt(keyboard, maxValPrompt);
      }
   }

   /* Prints the given prompt and returns the integer read by
   ** the given Scanner object.
   */
   private static int readInt(Scanner scanner, String prompt) {
      System.out.print(prompt);
      return scanner.nextInt();
   }

}