Stack and Queue <Nissan> | Editorial by abhinavkeshav

We have been given an array **A** of length **N** and an integer **K**.
We need to select **K** elements from the **start** of the array **A** or **end** of the array **A** or from both **start** and **end** such that the **sum** of the selected elements is **maximum**.
We can do this by first selecting all **K** elements from the **end** of the array **A** and none from the **start**, 
then selecting **K-1** elements from the **end** of the array **A** and **1** from the **start**, and so on and print the maximum of their sums.

This can be done be creating a **prefix sum** array named **count**.
Now we will loop through **K** and find the sum as **count[N]+count[i]-count[N-K+i].**
The **maximum** of these sums will be the answer.
If **K** is **1** then we need to print the **first** element of the array **A** , because it is asked to pop out at least one element from the stack.

Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        long a[]=new long[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextLong();
        }
        
        long count[]=new long[n+1];
        count[0]=0;
        
        for(int i=0;i<n;i++){
            count[i+1]=count[i]+a[i];
        }
        
        if(k!=1){
        long max=0;
        long sum=0;
        for(int i=1;i<=k;i++){
            sum=count[n]+count[i]-count[n-k+i];
            if(sum>max){
            max=sum;
            }
        }       
            System.out.println(max);
        }else{
            System.out.println(a[0]);
        }

Stack and Queue <Nissan> | Editorial by abhinavkeshav

Download submission

All caught up!

View submission

Is your resume even shortlisted?