forked from DhanushNehru/Hacktoberfest2025
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum_sum_of_Subarray.java
More file actions
30 lines (24 loc) · 1.2 KB
/
maximum_sum_of_Subarray.java
File metadata and controls
30 lines (24 loc) · 1.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class KadanesAlgorithm {
// Function to implement Kadane's Algorithm
public static int maxSubArraySum(int[] arr) {
// Initialize variables to track the current sum and the maximum sum
int maxSoFar = arr[0]; // Maximum sum found so far
int currentMax = arr[0]; // Maximum sum ending at the current position
// Loop through the array starting from the second element
for (int i = 1; i < arr.length; i++) {
// Update currentMax to be the maximum between the current element
// and the sum of the current element with the previous currentMax
currentMax = Math.max(arr[i], currentMax + arr[i]);
// Update maxSoFar if currentMax is larger
maxSoFar = Math.max(maxSoFar, currentMax);
}
return maxSoFar; // Return the maximum sum of the contiguous subarray
}
// Main function to test the algorithm
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // Sample array
// Call Kadane's algorithm and print the result
int maxSum = maxSubArraySum(arr);
System.out.println("Maximum contiguous subarray sum is: " + maxSum);
}
}