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