Q44 Largest Sum Subarray of Size at least K | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

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

class GFG {
	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)
        {
            long n = Long.parseLong(br.readLine().trim());
            long a[] = new long[(int)(n)];
            // long getAnswer[] = new long[(int)(n)];
            String inputLine[] = br.readLine().trim().split(" ");
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(inputLine[i]);
            }
            long k = Long.parseLong(br.readLine().trim());
            
            Compute obj = new Compute();
            System.out.println(obj.maxSumWithK(a, n, k));
            
        }
	}
}


// } Driver Code Ends


//User function Template for Java


class Compute {
    
    public long maxSumWithK(long arr[], long n, long k)
    {
        //applying kadanes and storing answers
        long msa[] = new long[arr.length];
        msa[0] = arr[0];
        long csum = arr[0]; 
        for(int i = 1 ; i < arr.length ; i++){
            
            if(csum > 0)
            csum += arr[i];
            
            else
            csum = arr[i];
            
            msa[i] = csum;
        }
        
        // for(int i = 0 ; i < arr.length ; i++)
        // System.out.print(msa[i] + " ");
        
        // System.out.println();
        
        //finding ans of first window
        long exactK = 0 , ans = Integer.MIN_VALUE;
        
        for(int i = 0 ; i < (int)k ; i++)
        exactK += arr[i];
        
        ans = Math.max(ans , exactK);
        //moving the window through rest of the array 
        
        for(int j = (int)k; j < arr.length ; j++){
            
            exactK += arr[j] - arr[j - (int)k];
            
            long atleastK = exactK + msa[j- (int)k];
            
            ans = Math.max(ans , exactK);
            ans = Math.max(ans , atleastK);
        }
        //returning answer
        return ans;
    }
}