Bird and maximum fruit gathering

Bird and maximum fruit gathering

  June 16, 2018    

---

Problem:

There are N trees in a circle. Each tree has a fruit value associated with it.  

A bird has to sit on a tree for 0.5 sec to gather all the fruits present on the tree and then the bird can move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she can’t pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.

We are given N and M (the total number of seconds the bird has), and the fruit values of the trees. We have to maximize the total fruit value that the bird can gather. The bird can start from any tree.


Idea is to find a window with size K as 0.5 to collect 0.5 sec to move so total 1 sec to collect and move to next element.
Now calculate first window and check whether we have reached to end of array , if so return total sum.
Else traverse till we have considered every i as starting position as it is circular array then we can move from n to 0 ,1 ... 
so we keep track on that using start variable.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class dmg
 {
  public static long fn(int a[],int n,int k)
  {
      int i=0;
      long cursum=0,res=0;
      for(;i<k && i<n;++i)
      {
          cursum+=a[i];
      }
      res=cursum;
      if(i==n)
      return res;
      int start=0;
      for(;start<n;i=(i+1)%n)
      {
          cursum+=a[i];
          cursum-=a[start++];
          if(cursum>res)
          res=cursum;
      }
      return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int k=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n,k));
}
}
}