Maximum Subarray Sum (Kadanes Algorithm)

This program finds maximum subarray sum using Kadanes algorithm.

Problem Statement

Write a Java program to find maximum subarray sum in an integer array.

Source Code

1 public class MaximumSubarraySum {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Maximum Subarray Sum");
4 int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
5 int maxSoFar=arr[0], maxEndingHere=arr[0];
6 for(int i=1;i<arr.length;i++){
7 maxEndingHere = Math.max(arr[i], maxEndingHere+arr[i]);
8 maxSoFar = Math.max(maxSoFar, maxEndingHere);
9 }
10 System.out.println("Maximum subarray sum: "+maxSoFar);
11 }
12 }

Program Output

Eduinq Maximum Subarray Sum
Maximum subarray sum: 6

Explanation

Kadanes algorithm tracks maximum sum ending at each index. - maxEndingHere updated with current element or extended sum. - maxSoFar stores global maximum. - Together finds maximum subarray sum efficiently. Conclusion: Demonstrates Kadanes algorithm for maximum subarray sum.

Quick Links to Explore