Maximum Subarray Sum (Kadane's Algorithm)
This program finds maximum subarray sum using Kadane's 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
Kadane's algorithm tracks the maximum sum ending at each index using maxEndingHere, which is either the current element alone or extended from the previous sum, while maxSoFar retains the global best, efficiently finding the maximum subarray sum.