MaximumSubArrayWithGivenSum

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        int arr = firstNegative(new int[] {4,1,1,1,2,3,5}, 7, 5);
        System.out.print(arr);
    }
	public static int firstNegative(int[] arr, int n, int k) {
        // Write your code here.
        int max =0, sum = 0;
		int start=0,end=0;
        while(end < n)
        {
            sum += arr[end];
            System.out.println("SUm " + sum);
            if(sum > k) 
            {
                while(sum > k)
                sum -= arr[start++];
            }
            if(sum == k)
            {
                max = Math.max(max, end - start + 1);
                System.out.println("Max " + max + "end, start " + end +" " + start);
            }
            
            end++;
        }
        return max;
	}
    /* More optimized
     * public static int[] firstNegative(int[] arr, int n, int k) {
        // Write your code here.
		Queue<Integer> l = new LinkedList<>();
        int res[] = new int[n - k + 1];
		int start=0,end=0;
        for(; end<k-1;end++)
        {
            while(l.size() > 0 && l.peek() < arr[end])
                {
                    l.poll();
                }
            //Calculation
            l.add(arr[end]);
        }
        while(end < n)
        {
            
            while(l.size() > 0 && l.peek() < arr[end])
                {
                    l.poll();
                }
            //Calculation
            l.add(arr[end++]);
            
            res[start] = l.peek();
            if(arr[start] == l.peek())
            {
                l.poll();
            }
            start++;
        }
        return res;
	}
     */
}