Kadane's Algorithm .txt

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG1 {
	public static void main (String[] args) {
	    Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0)
		{
		    int n=sc.nextInt();
		    int array[]=new int[n];
		    for(int i=0;i<n;i++)
		    {
		        array[i]=sc.nextInt();
		    }
		    int max=Integer.MIN_VALUE;
			
		    int min=Integer.MIN_VALUE;
		    int presum=array[0];
			int cursum=array[0];
				for(int j=1;j<n;j++)
				{
				cursum=Math.max(array[j],cursum+array[j]);
					if(presum<=cursum)
						presum=cursum;
				}
			System.out.println(presum);
		}
	}
}