Kadane Algorithm

 Given an integer array arr[]. You need to find the maximum sum of a subarray.

Examples:

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]

Output: 11

Explanation: The subarray {7, -1, 2, 3} has the largest sum 11.

Input: arr[] = [-2, -4]

Output: -2

Explanation: The subarray {-2} has the largest sum -2.

Input: arr[] = [5, 4, 1, 7, 8]

Output: 25

Explanation: The subarray {5, 4, 1, 7, 8} has the largest sum 25.

//{ Driver Code Starts

// Initial Template for Java

import java.io.*;

import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine().trim()); // Inputting the testcases

        while (t-- > 0) {

            String line = br.readLine();

            String[] tokens = line.split(" ");

            // Create an ArrayList to store the integers

            ArrayList<Integer> array = new ArrayList<>();

            // Parse the tokens into integers and add to the array

            for (String token : tokens) {

                array.add(Integer.parseInt(token));

            }

            int[] arr = new int[array.size()];

            int idx = 0;

            for (int i : array) arr[idx++] = i;

            Solution obj = new Solution();

            // calling maxSubarraySum() function

            System.out.println(obj.maxSubarraySum(arr));

            System.out.println("~");

        }

    }

}

// } Driver Code Ends

class Solution {

    int maxSubarraySum(int[] arr) {

        // Your code here

        

       int maxi = Integer.MIN_VALUE;  // Stores the maximum sum

        int currentSum = 0;

        for (int num : arr) {

            currentSum += num;  // Add current element to the sum

            maxi = Math.max(maxi, currentSum);  // Update the maximum sum

            if (currentSum < 0) {

                currentSum = 0;  // Reset if sum becomes negative

            }

        }

        return maxi;

    }

}