Package org.drip.graph.subarray

Class Kadane

java.lang.Object
org.drip.graph.subarray.Kadane
public class Kadane
extends java.lang.Object
Kadane implements the Kadane Algorithm for the Maximum Sub-array Problem. The References are:

  • Bentley, J. (1984): Programming Pearls: Algorithm Design Techniques Communications of the ACM 27 (9) 865-873
  • Bentley, J. (1989): Programming Pearls nd Edition Addison-Wesley Reading MA
  • Gries, D. (1982): A Note on a Standard Strategy for developing Loop Invariants and Loops Science of Computer Programming 2 (3) 207-214
  • Takaoka, T. (2002): Efficient Algorithms for the Maximum Sub-array Problem by Distance Matrix Multiplication https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub
  • Wikipedia (2020): Maximum Sub-array Problem https://en.wikipedia.org/wiki/Maximum_subarray_problem




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    Kadane​(int[] numberArray, boolean disallowEmptyArray)
    Kadane Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean disallowEmptyArray()
    Retrieve the Flag indicating whether Empty Array should be allowed
    int[] maximumSubarraySequence()
    Retrieve the Start/End Indexes of the Maximum Sub-array Sequence
    int maximumSubArraySum()
    Compute the Maximum Sub-array Sum
    int[] numberArray()
    Retrieve the Number Array

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Kadane

      public Kadane​(int[] numberArray, boolean disallowEmptyArray) throws java.lang.Exception
      Kadane Constructor
      Parameters:
      numberArray - The Input Number Array
      disallowEmptyArray - TRUE - Disallow Empty Sub-array
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • numberArray

      public int[] numberArray()
      Retrieve the Number Array
      Returns:
      The Number Array

    • disallowEmptyArray

      public boolean disallowEmptyArray()
      Retrieve the Flag indicating whether Empty Array should be allowed
      Returns:
      TRUE - Empty Array should be disallowed

    • maximumSubArraySum

      public int maximumSubArraySum()
      Compute the Maximum Sub-array Sum
      Returns:
      The Maximum Sub-array Sum

    • maximumSubarraySequence

      public int[] maximumSubarraySequence()
      Retrieve the Start/End Indexes of the Maximum Sub-array Sequence
      Returns:
      Start/End Indexes of the Maximum Sub-array Sequence