Maximum Subarray Sum in Java: Kadane's Algorithm

Let's learn how to efficiently find the maximum subarray sum using Kadane's Algorithm in Java.

Problem Statement:

Given an array of size N, write a Java program to determine the maximum sum of a contiguous subarray using Kadane's Algorithm.

Example:

<code>Input:
n = 5
arr[] = 1, 2, 3, -2, 5

Output:
Maximum Subarray sum is: 9</code>

Understanding Kadane's Algorithm:

Kadane's Algorithm provides an efficient O(n) time complexity solution for finding the maximum subarray sum.

Steps:

1. Initialize two variables: currentSum (to track the sum of the current subarray) and maxSum (to store the maximum sum encountered so far). Set currentSum to 0 and maxSum to the smallest possible integer value (e.g., Integer.MIN_VALUE).

2. Iterate through the array: For each element arr[i], add its value to currentSum.

3. Update maxSum: After each addition, update maxSum by taking the maximum of maxSum and currentSum.

4. Reset currentSum: If currentSum becomes negative, reset it to 0. This is crucial because a negative currentSum indicates that including the previous elements doesn't contribute to a larger sum; it's better to start a new subarray from the current element.

Java Code:

import java.util.Scanner;

public class KadaneAlgo {
    public static int findMaxSubArraySum(int[] arr, int n) {
        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE; // Initialize to the smallest possible integer

        for (int i = 0; i < n; i++) {
            currentSum += arr[i];
            maxSum = Math.max(maxSum, currentSum); // Update maxSum if necessary
            if (currentSum < 0) {
                currentSum = 0; // Reset currentSum if it becomes negative
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.print("Enter the elements of the array: ");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int maxSum = findMaxSubArraySum(arr, n);
        System.out.println("Maximum Subarray sum is: " + maxSum);
        scanner.close();
    }
}

Output (Example):

<code>Enter the size of the array: 5
Enter the elements of the array: 1 2 3 -2 5
Maximum Subarray sum is: 9</code>

The above is the detailed content of Maximum Subarray Sum in Java: Kadane's Algorithm. For more information, please follow other related articles on the PHP Chinese website!