# Kadane's Algorithm

## Kadane's Algorithm: Finding the Maximum Contiguous Subarray Sum in Java

The problem of finding the maximum sum of a contiguous subarray within a given array of integers is a classic challenge in computer science. This post explores two approaches to solving this problem in Java: a brute-force method and the highly efficient Kadane's Algorithm. We'll compare their time complexities and demonstrate their implementations.

**The Problem:**

Given an array of integers (which can include positive, negative, and zero values), find the contiguous subarray with the largest sum and return that sum.

**1\. Brute-Force Approach (O(n^2) Time Complexity)**

The brute-force approach involves checking the sum of all possible subarrays. We use nested loops: the outer loop selects the starting index, and the inner loop calculates the sum of all subarrays starting from that index.

Java

```java
public class MaxSubarraySum {

    public static int maxSubarraySumBruteForce(int[] arr) {
        int maxSum = Integer.MIN_VALUE; // Initialize with the smallest possible integer

        for (int i = 0; i < arr.length; i++) { // Outer loop: starting index
            for (int j = i; j < arr.length; j++) { // Inner loop: ending index
                int currentSum = 0;
                for (int k = i; k <= j; k++) { // Calculate sum of subarray from i to j
                    currentSum += arr[k];
                }
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
    // ... (Kadane's Algorithm will go here)

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSumBruteForce = maxSubarraySumBruteForce(arr);
        System.out.println("Maximum Subarray Sum (Brute Force): " + maxSumBruteForce);


        int maxSumKadane = maxSubarraySumKadane(arr);
        System.out.println("Maximum Subarray Sum (Kadane's Algorithm): " + maxSumKadane);

    }
}
```

* **Time Complexity:** O(n^2) due to the nested loops.
    
* **Space Complexity:** O(1) as we use only constant extra space.
    
* **Disadvantage:** Inefficient for larger arrays.
    

**2\. Kadane's Algorithm (O(n) Time Complexity)**

Kadane's algorithm provides a much more efficient solution with linear time complexity. The core idea is to keep track of two values:

* `max_so_far`: Stores the maximum sum found so far.
    
* `current_max`: Stores the maximum sum ending at the current position.
    

Java

```java
public static int maxSubarraySumKadane(int[] arr) {
    int maxSoFar = Integer.MIN_VALUE;
    int currentMax = 0;

    for (int num : arr) {
        currentMax += num;

        if (currentMax < 0) {
            currentMax = 0;  // Reset if the current sum becomes negative
        }

        maxSoFar = Math.max(maxSoFar, currentMax); // Update max_so_far
    }
    return maxSoFar;
}
```

* **Time Complexity:** O(n) as we iterate through the array only once.
    
* **Space Complexity:** O(1) as we use only constant extra space.
    
* **Advantage:** Highly efficient, even for large datasets.
    

**Explanation of Kadane's Algorithm:**

The algorithm's key insight is that a negative subarray sum will never contribute to a larger overall sum. If `current_max` becomes negative, we reset it to 0, effectively starting a new subarray from the next element. We continually update `max_so_far` to keep track of the largest sum encountered.

**Which Approach to Use?**

Kadane's Algorithm is the clear winner due to its superior time complexity. For any array of significant size, the brute-force approach will be considerably slower. Kadane's algorithm is the standard and most efficient way to solve the maximum contiguous subarray sum problem.