Kadane's Algorithm

//Kadane's Algorithm

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());

        while(t-- > 0) {
            String line = br.readLine();
            String[] tokens = line.split(" ");
            ArrayList<Integer> array = new ArrayList<>();

            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();
            System.out.println(obj.maxSubarraySum(arr));
        }
    }
}

class Solution {
    int maxSubarraySum(int[] arr) {
        int res = arr[0];
        int maxEnding = arr[0];

        for(int i = 1; i < arr.length; i++) {
            maxEnding = Math.max(maxEnding + arr[i], arr[i]);
            res = Math.max(res, maxEnding);
        }
        
        return res;
    }
}