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.