Class MaxSum

java.lang.Object
topics.divideconquer.maxsum.MaxSum
public class MaxSum extends Object

Maximum Subarray Sum

Evaluates a sequence of numbers to find the contiguous sub-sequence that produces the largest possible sum. This class demonstrates the architectural evolution from a brute-force Cubic approach to a Logarithmic Divide invalid input: '&' Conquer approach.

Author:
vicegd

  • Constructor Details

    • MaxSum

      public MaxSum()

  • Method Details

    • maxSubarrayCubic

      public int maxSubarrayCubic(int[] v)

      1. Naive Cubic Approach O(N³)

      Tests every possible combination of start and end indices (i and j), and uses a third nested loop (k) to calculate the sum from scratch every time.

      Parameters:
      v - Array of integers.
      Returns:
      The maximum contiguous sum.

    • maxSubarrayQuadratic

      public int maxSubarrayQuadratic(int[] v)

      2. Optimized Quadratic Approach O(N²)

      Eliminates the third loop. It recognizes that the sum of array[i..j] is simply array[i..j-1] + array[j]. It accumulates the sum dynamically.

      Parameters:
      v - Array of integers.
      Returns:
      The maximum contiguous sum.

    • maxSubarrayDivideAndConquer

      public int maxSubarrayDivideAndConquer(int[] v)

      3. Divide invalid input: '&' Conquer Approach O(N log N)

      Divides the array into two halves recursively. The maximum subarray must lie: 1. Entirely in the left half. 2. Entirely in the right half. 3. Crossing the midpoint.

      Parameters:
      v - Array of integers.
      Returns:
      The maximum contiguous sum.