Untitled
Anonymous
Plain Text
10/24/2025 5:12 PM
1.5 KB
13
Indexable
Never
package LogicalProblems;
import java.util.Scanner;
public class KadaneAlgo {
/**
*This class Takes an integer array nums, find the subarray with the largest sum and return the sum of the elements present in that subarray.
* A subarray is a contiguous non-empty sequence of elements within an array.
*
* Examples:
* Input: nums = [2, 3, 5, -2, 7, -4]
* Output: 15
* Explanation:
* The subarray from index 0 to index 4 has the largest sum = 15
*
* Input: nums = [-2, -3, -7, -2, -10, -4]
* Output: -2
* Explanation:
* The element on index 0 or index 3 make up the largest sum when taken as a subarray
*/
public static int kadaneAlgo(int[] nums){
int max = -999999;
int sum = 0;
for (int i = 0; i < nums.length; i++){
sum += nums[i];
if (sum > max) {
max=sum;
}
if (sum < 0){
sum = 0;
}
}
return max;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.print(" ENTER ARRYA SIZE -> ");
int size = s.nextInt();
int arr[] = new int[size];
System.out.println("ENTER ARRAY ELEMENTS -> ");
for (int i = 0; i < size; i++) {
arr[i] = s.nextInt();
}
System.out.println("ENTER X -> " );
int x = s.nextInt();
System.out.print("LOWER BOUND -> " + kadaneAlgo(arr));
}
}
Editor is loading...
Leave a Comment